#include <iostream>
#include <vector>
using namespace std;

// Node structure for doubly linked list
struct Node {
    int data;
    Node* next;
    Node* prev;
    Node(int x) : data(x), next(nullptr), prev(nullptr) {}
};

class Solution {
public:
    Node* constructDLL(vector<int>& arr) {
        if(arr.empty()) return nullptr;
        
        Node* head = new Node(arr[0]);
        Node* prev = nullptr;
        Node* current = head;
        
        for(int i = 1; i < arr.size(); i++) {
            current->next = new Node(arr[i]);
            current->next->prev = current;
            current = current->next;
        }
        
        return head;
    }
};

// Helper function to print DLL forward
void printForward(Node* head) {
    Node* current = head;
    while(current) {
        cout << current->data;
        if(current->next) cout << " <-> ";
        current = current->next;
    }
    cout << endl;
}

// Helper function to print DLL backward
void printBackward(Node* tail) {
    Node* current = tail;
    while(current) {
        cout << current->data;
        if(current->prev) cout << " <-> ";
        current = current->prev;
    }
    cout << endl;
}

// Helper function to delete DLL
void deleteDLL(Node* head) {
    while(head) {
        Node* temp = head;
        head = head->next;
        delete temp;
    }
}

int main() {
    Solution sol;
    
    // Test Case 1: Normal case
    vector<int> arr1 = {1, 2, 3, 4, 5};
    Node* dll1 = sol.constructDLL(arr1);
    cout << "Test 1 - Forward: ";
    printForward(dll1);
    
    // Get tail to test backward traversal
    Node* tail1 = dll1;
    while(tail1->next) tail1 = tail1->next;
    cout << "Test 1 - Backward: ";
    printBackward(tail1);
    deleteDLL(dll1);
    
    // Test Case 2: Single element
    vector<int> arr2 = {10};
    Node* dll2 = sol.constructDLL(arr2);
    cout << "\nTest 2 - Forward: ";
    printForward(dll2);
    cout << "Test 2 - Backward: ";
    printBackward(dll2);  // Same as forward for single node
    deleteDLL(dll2);
    
    // Test Case 3: Empty list
    vector<int> arr3 = {};
    Node* dll3 = sol.constructDLL(arr3);
    cout << "\nTest 3 - Empty list: ";
    printForward(dll3);  // Should print nothing
    deleteDLL(dll3);
    
    return 0;
}