LIST

#include <iostream>
using namespace std;
 typedef struct element{
   int key;
   struct element *next;
 } *list;
 list p = NULL, q;
 list to_one(list a, list b){
   if (a == NULL) return b;
   else {
     q = a;
     while (q -> next != NULL ) q = q -> next;
     q -> next = b;
   }
   return a;
 }

 list qsort(list a){
   if (a == NULL)
    return a;
  list help1 = NULL, help2 = NULL, help3 = NULL, zachem_tak_zhit;
  q = a;
  int k = a-> key;
  while (q != NULL){
    zachem_tak_zhit = q -> next;
    if (q -> key < k){
      q -> next = help1;
      help1 = q;
    }
    else if (q -> key > k){
      q -> next = help2;
      help2 = q;
    }
    else {
      q -> next = help3;
      help3 = q;
    }
    q = zachem_tak_zhit;
  }
  help1 = qsort(help1);
  help2 = qsort(help2);
  help3 = to_one(help3, help2);
  help1 = to_one(help1, help3);
  return help1;
 }

 list merge_sort(list a,int L, int R){
   if (a == NULL)
    return a;
   int M = (R + L) / 2;
   list help1 = NULL, help2 = NULL, q = a, help3 = NULL;
   for (int i = L; i <= M; ++i){
     q -> next = help1;
     help1 = q;
   }
   help1->next= NULL;
   for (int i = M + 1; i <= R; ++i){
     q -> next = help2;
     help2 = q;
   }
   help2->next = NULL;
   cout << M << endl;
   list zhozho = help3;
   help1 = merge_sort(help1, L, M);
   help2 = merge_sort(help2, M + 1, R);
   if (help1 -> key < help2->key){
       help3 = help1;
       help1 = help1 -> next;
   }
   else {
     help3 = help2;
     help2 = help2 -> next;
   }
   for (int i = L; i <= R; ++i){
     if (help1->next == NULL){
       help3 -> next = help2;
       break;
     }
     if (help2->next == NULL){
       help3 -> next = help1;
       break;
     }
     if (help1 -> key < help2->key){
       help3 -> next = help1;
       help1 = help3;
   }
   else {
     help3 -> next = help2;
     help2 = help3;
    }
   }
  return zhozho;
 }
int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) {
        q = new element;
        cin >> q->key;
        q->next = p;
        p = q;
    }
    p = merge_sort(p,0,n-1);
    q = p;
    while (q != NULL) {
        cout << q->key << ' ';
        q = q->next;
    }
    return 0;
}