#include <iostream>
using namespace std;

class Node
{
public:
  int data;
  Node* next;
  
  Node(int data)
  {
    this->data = data;
    this->next = nullptr;
  }
};

class LinkedList
{
private:
  Node* head;
  
  Node* GetTail(Node* start)
  {
    while(start->next != nullptr)
      start = start->next;
      
    return start;
  }
  
  Node* Partition(Node* start, Node* end, Node** newHead, Node** newEnd)
  {
    Node* pivot = end;
    Node* prev = nullptr, *cur = start, *tail = pivot;
    
    while(cur != pivot)
    {
      if(cur->data < pivot->data)
      {
        if(*newHead == nullptr)
          *newHead = cur;
          
        prev = cur;
        cur = cur->next;
      }
      else
      {
        if(prev != nullptr)
          prev->next = cur->next;
        
        Node* temp = cur->next;
        cur->next = nullptr;
        tail->next = cur;
        tail = cur;
        cur = temp;
      }
    }
    
    if(*newHead == nullptr)
      *newHead = pivot;
      
    *newEnd = tail;
    
    return pivot;
  }
  
  Node* QuickSortAlgo(Node* start, Node* end)
  {
    if(!start || start == end)
      return start;
      
    Node* newHead = nullptr, *newEnd = nullptr;
    
    Node* pivot = Partition(start, end, &newHead, &newEnd);
    
    if(newHead != pivot)
    {
      Node* temp = newHead;
      while(temp->next != pivot)
        temp = temp->next;
      temp->next = nullptr;
      
      newHead = QuickSortAlgo(newHead, temp);
      
      temp = GetTail(newHead);
      temp->next = pivot;
    }
    
    pivot->next = QuickSortAlgo(pivot->next, newEnd);
    
    return newHead;
  }
  
public:
  void InsertAtEnd(int data)
  {
    Node* newNode = new Node(data);
    if(!head)
    {
      head = newNode;
      return;
    }
    
    Node* last = head;
    while(last->next != nullptr)
      last = last->next;
      
    last->next = newNode;
  }
  
  void QuickSort()
  {
    head = QuickSortAlgo(head, GetTail(head));
  }
  
  void PrintList()
  {
    Node* temp = head;
    while(temp != nullptr)
    {
      cout << temp->data << " -> ";
      temp = temp->next;
    }
    
    cout << "null" << endl;
  }
};

int main() 
{
  int n;
  cin >> n;
  
  LinkedList* list = new LinkedList();
  
  for(int i = 0; i < n; ++i)
  {
    int data;
    cin >> data;
    list->InsertAtEnd(data);
  }
  
  cout << "Unsorted list:" << endl;
  list->PrintList();
  
  list->QuickSort();
  
  cout << "\nSorted list:" << endl;
  list->PrintList();
  
  delete(list);
  return 0;
}