Untitled

class DoublyLinkedList {
    class Node {
        int data;
        Node prev;
        Node next;

        Node(int data) {
            this.data = data;
            this.prev = null;
            this.next = null;
        }
    }

    Node head, tail;

    DoublyLinkedList() {
        head = null;
        tail = null;
    }

    // Function to add a new node at the end of the list
    void addNode(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
    }

    // Function to split the doubly linked list into two halves
    Node split(Node head) {
        Node slow = head;
        Node fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        Node secondHalf = slow.next;
        slow.next = null;
        if (secondHalf != null) {
            secondHalf.prev = null;
        }
        return secondHalf;
    }

    // Function to merge two sorted halves
    Node merge(Node first, Node second) {
        if (first == null) return second;
        if (second == null) return first;

        if (first.data <= second.data) {
            first.next = merge(first.next, second);
            first.next.prev = first;
            first.prev = null;
            return first;
        } else {
            second.next = merge(first, second.next);
            second.next.prev = second;
            second.prev = null;
            return second;
        }
    }

    // Merge sort function for doubly linked list
    Node mergeSort(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node secondHalf = split(head);
        head = mergeSort(head);
        secondHalf = mergeSort(secondHalf);
        return merge(head, secondHalf);
    }

    // Function to print the list from head to tail
    void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    // Function to print the list from tail to head
    void printListReverse() {
        Node current = tail;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.prev;
        }
        System.out.println();
    }

    // Function to sort the list
    void sort() {
        if (head != null) {
            head = mergeSort(head);
            // Update tail pointer
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            tail = current;
        }
    }

    public static void main(String[] args) {
        java.util.Scanner sc = new java.util.Scanner(System.in);
        int n = sc.nextInt();
        DoublyLinkedList dll = new DoublyLinkedList();
        for (int i = 0; i < n; i++) {
            dll.addNode(sc.nextInt());
        }

        // Sort the list
        dll.sort();

        // Print the sorted list
        dll.printList();

        // Print the reverse sorted list
        dll.printListReverse();

        sc.close();
    }
}