#include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <ctime>

 using namespace std;

 #define MAXN 100005

 int a[MAXN], b[MAXN];

 int c[MAXN];

 int ans, n;

 void merge(int *a, int l, int r) {

     int mid = (l+r)>>;

     int i = l, j = mid+;

     int n = ;

     while (i<=mid && j<=r) {

         if (a[i] <= a[j]) {

             c[n++] = a[i++];

         } else {

             c[n++] = a[j++];

             ans += (mid-i+);

         }

     }

     while (i <= mid)

         c[n++] = a[i++];

     while (j <= r)

         c[n++] = a[j++];

     for (i=, j=l; i<n; ++i, ++j)

         a[j] = c[i];

 }

 void mergeSort(int *a, int l, int r) {

     int mid = (l+r)>>;

     if (l >= r)

         return ;

     mergeSort(a, l, mid);

     mergeSort(a, mid+, r);

     merge(a, l, r);

 }

 void bruteSolve(int *b, int l, int r) {

     int i, j;

     for (i=l; i<=r; ++i) {

         for (j=l; j<=i; ++j) {

             if (b[j] > b[i])

                 ++ans;

         }

     }

 }

 void init() {

     int i;

     n = rand()%(MAXN-)+;

     for (i=; i<=n; ++i) {

         a[i] = rand();

         b[i] = a[i];

     }

 }

 void solve() {

     clock_t beg, end;

     int tmp;

     ans = ;

     beg = clock();

     mergeSort(a, , n);

     end = clock();

     printf("nlgn: ans  = %d\n", ans);

     printf("      time = %.2lf\n", (double)(end-beg)/CLOCKS_PER_SEC);

     tmp = ans;

     ans = ;

     beg = clock();

     bruteSolve(b, , n);

     end = clock();

     printf("n*n : ans  = %d\n", ans);

     printf("      time = %.2lf\n", (double)(end-beg)/CLOCKS_PER_SEC);

     if (tmp != ans)

         printf("**** wrong ****\n");

     printf("\n");

 }

 int main() {

     int t = ;

     while (t--) {

         init();

         solve();

     }

     return ;

 }