Merge

#include<bits/stdc++.h>
using namespace std;

///-----------------------------------compiler optimizer--------------------------------------------//
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization("unroll-loops")

///--------------------------------------data type--------------------------------------------------//
typedef long long int lli;

///----------------------------------------stack-----------------------------------------------------//
typedef stack <int> STI;
typedef stack <char> STC;
typedef stack <string> STS;

///----------------------------------------queue------------------------------------------------------//
typedef queue <int> QI;
typedef queue <char> QC;
typedef queue <string> QS;
typedef priority_queue <int> PQI;

///---------------------------------------dequeue-----------------------------------------------------//
typedef deque <int> DI;
typedef deque <char> DC;

///---------------------------------------set------------------------------------------------------//
typedef set <int> SI;
typedef set <string> SS;
typedef set <char> SC;
typedef multiset <int> MSI;

///----------------------------------------map------------------------------------------------------//
typedef map <int, int> MP;
typedef map <string, int> MPSI;
typedef map <char, int> MPCI;

///----------------------------------------pair------------------------------------------------------//
typedef pair <int, int> PII;

///----------------------------------------vector------------------------------------------------------//
typedef vector <int> VI;
typedef vector <char> VC;
typedef vector <string> VS;
typedef vector <lli> VLLI;

///----------------------------------------constant------------------------------------------//

#define MAX                 1E9 + 5
#define MIN                 -1E9 - 5
#define INF                 1E18 + 5
#define MOD                 10000007
#define py                  acos(-1.0)  /// 3.1415926535897932

///-------------------------------------------------------------------------------//
#define pp1(A)              printf("%d\n", A)
#define ppl(A)              printf("%lld\n", A)
#define pp2(A,B)            printf("%d %d\n", A, B)
#define pp3(A,B,C)          printf("%d %d %d\n", A, B, C)

#define ss1(A)              scanf("%d", &A)
#define ssl(A)              scanf("%lld", &A)
#define ss2(A,B)            scanf("%d %d", &A, &B)
#define ss3(A,B,C)          scanf("%d %d %d", &A, &B, &C)

///---------------------------------------------------------------------------//

#define pf                  push_front
#define pb                  push_back
#define popb                pop_back
#define popf                pop_front

#define ub                  upper_bound
#define lb                  lower_bound

#define itr                 iterator
#define ritr                reverse_iterator

#define mk                  make_pair
#define ff                  first
#define ss                  second

///---------------------------------------------------------------------------//
#define endl                "\n"
#define gap                 " "
#define END                 return 0
#define line                printf( "\n")
#define yes                 printf( "YES\n")
#define no                  printf( "NO\n")

#define Before              printf( "Before  \n")
#define After               printf( "After  \n")

#define enter1              printf( "Entered 1\n")
#define enter2              printf( "Entered 2\n")
#define enter3              printf( "Entered 3\n")

#define Case(k,n)           printf( "Case %d: %d\n", k, n)
#define Casell(k,n)         printf( "Case %lld: %lld\n", k, n)

#define fastIO              cin.tie(0), cout.tie(0)
#define TS                  template < typename T >
#define TP                  template < typename F, typename S >
#define TM                  template<typename T1, typename... T2>
#define ddd(args...)        do { cerr << #args << "-> " ;  show(args); } while(0); cerr<< endl ;

///-----------------------------------------------------------------------------//
#define sq(a)               (a) * (a)
#define SZ(a)               (int) a.size()
#define all(a)              (a).begin(), (a).end()
#define rall(a)             (a).rbegin(), (a).rend()

#define mem(x, y)           memset(x, y, sizeof(x))
#define unq(v)              v.erase( unique( all(v)), v.end())
#define rev(v)              reverse( all(v))
#define sortV(v)            sort( all(v))
#define sortA(a,n)          sort(a, a+n)

#define to_upper(s)         transform( s.begin(), s.end(), s.begin(), ::toupper)
#define to_lower(s)         transform( s.begin(), s.end(), s.begin(), ::tolower)
#define to_int(s)           stoi(s)

///--------------------------------------------------------------------------------//
#define Erase(V,I)          (V).erase((V).begin()+I)
#define Insert(V,I,M)       (V).insert((V).begin()+I,M)

#define read()              freopen("input.txt", "r", stdin)
#define write()             freopen("output.txt", "w", stdout)

///-------------------------------------------------------------------------------------------------------------------------------//
#define loop(i, n)          for(int i = 0; i < n; i++)
#define loops(i, x, n)      for(int i = x; i < n; i++)
#define loopr(i, n)         for(int i = n-1; i >= 0; i--)
#define loopt(i, n)         for(int i = 1; i <= n; i++)

#define autoo(s)            for(auto it = s.begin(); it != s.end(); it++)

#define vin(V, N)           for(int i = 0; i < N; i++){ int X; ss1(X); V.pb(X); }
#define vinll(V, N)         for(int i = 0; i < N; i++){ lli X; ssl(X); V.pb(X); }

#define ain(A, N)           for(int i = 0; i < N; i++){ ss1(A[i]); }
#define ainll(A, N)         for(int i = 0; i < N; i++){ ssl(A[i]); }

#define aout(A, N)          for(int i = 0; i < N; i++){ printf("%d", A[i]); if (i < N-1) printf(" "); else printf("\n"); }
#define vout(v)             for(int i = 0; i < v.size(); i++) { printf("%d", v[i]); if(i < v.size() - 1) printf(" "); else printf("\n");}

///--------------------------------------------------Debugging-----------------------------------------------------------------//

TS void show (const T& v) { cerr << v << ' ' ;}

TM void show (const T1& first, const T2&... rest){ show(first); show(rest...); }

TP ostream& operator << (ostream& os, const pair<F,S>& p){return os<<"("<< p.ff << ", " << p.ss <<")" ;}

TS ostream& operator << (ostream& os, const vector<T>& v){os << "{"; typename vector< T >::const_iterator it;
    for(it = v.begin(); it != v.end(); it++) {if( it != v.begin() )os << ", "; os<<*it; } return os<<"}";}

TS ostream& operator << (ostream& os, const set<T>& v){os << "["; typename set<T>::const_iterator it;
    for(it = v.begin(); it != v.end(); it++){ if(it != v.begin())os<<", ";os <<*it; } return os <<"]"; }

TS ostream& operator << (ostream& os, const multiset<T>& v){os << "["; typename multiset<T>::const_iterator it;
    for(it = v.begin(); it != v.end(); it++){ if(it != v.begin())os<<", ";os <<*it; } return os <<"]"; }

TP ostream& operator<<(ostream& os,const map<F,S>& v){os<<"["; typename map<F,S>::const_iterator it;
    for(it = v.begin(); it != v.end(); it++){if(it != v.begin())os << ", "; os << it->ff <<" = " << it->ss; } return os<<"]";}

//-------------------------------------------------------------------------------------------------------------------------------//

lli lcm(lli a, lli b){
    return a * (b / __gcd(a, b));
}

///----------------------graph moves----------------*/
int dr[] = {+1, -1, +0, +0};
int dc[] = {+0, +0, +1, -1};

///----------------------kings moves-----------------*/
int X[] = {+0, +0, +1, -1, -1, +1, -1, +1};
int Y[] = {-1, +1, +0, +0, +1, +1, -1, -1};

///----------------------knights moves----------------*/
int KX[] = {-2, -2, -1, -1,  1,  1,  2,  2};
int KY[] = {-1,  1, -2,  2, -2,  2, -1,  1};

///-----------------------------------template------------------------------------------------//
const int N = 100005;
int n,  a[N];
int cnt = 0;

void merge1(int l, int m, int r){
    int n1 = m-l+1;
    int n2 = r-m;
    cout << "up " << l << gap << r << endl;

    int left[n1], right[n2];
    cout << "left " << endl;

    loop(i, n1){
        left[i] = a[l+i];
        cout << left[i] << " ";
    }
    line;
    cout << "right " << endl;
    loop(i, n2){
        right[i] = a[m+1+i];
        cout << right[i] << " ";
    }
    line;

    int i = 0;
    int j = 0;
    int k = l;


    while(i < n1 and j < n2){
        if(left[i] <= right[j]){
            a[k++] = left[i++];
        }
        else {
            cnt += (n1 - i);
            a[k++] = right[j++];
        }
    }
    while(i < n1) a[k++] = left[i++];

    while(j < n2) a[k++] = right[j++];
    cout << "cnt " << cnt << endl;
    line;
    line;
}

void mergeSort(int l, int r){

    if(l >= r) return;

    int md = l + (r-l) / 2;

    mergeSort(l, md);
    mergeSort(md+1, r);

    merge1(l, md, r);
}

int main()
{
    #ifndef ONLINE_JUDGE
    read();
    write();
    #endif // ONLINE_JUDGE
   // fastIO;
   cin >> n;

   loop(i, n) cin >> a[i];

//   loop(i, n){
//    cout << a[i] << gap;
//   }
   mergeSort(0, n-1);

   loop(i, n){
    cout << a[i] << gap;
   }
   line;
   cout << cnt << endl;


}