#include <bits/stdc++.h>
using namespace std;
vector<int> vec;
int n;
 
int recur(int l, int r){
	int ans = 0;
	if(l + 1 >= r){
		return ans;
	}
	int mid = (l + r) / 2;
	ans += recur(l, mid);
	ans += recur(mid, r);
	int ans1 = ans;
	cout << l << " " << r << endl; 
	for(int i = 1, j = 0; i <= r; i++){
		while(j < r && j < i){
			if(vec[i] < vec[j]) ans1++;
			j++;
		}
 
	}
	inplace_merge(vec.begin() + l, vec.begin() + mid, vec.begin() + r);
	return ans1; 
 
 
 
}
signed main(){
 
	cin >> n;
	for(int i = 0; i < n; i++){
		int num; 
		cin >> num;
		vec.push_back(num);
	}
	cout << recur(0, n) << endl; 
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnZlY3RvcjxpbnQ+IHZlYzsKaW50IG47CgppbnQgcmVjdXIoaW50IGwsIGludCByKXsKCWludCBhbnMgPSAwOwoJaWYobCArIDEgPj0gcil7CgkJcmV0dXJuIGFuczsKCX0KCWludCBtaWQgPSAobCArIHIpIC8gMjsKCWFucyArPSByZWN1cihsLCBtaWQpOwoJYW5zICs9IHJlY3VyKG1pZCwgcik7CglpbnQgYW5zMSA9IGFuczsKCWNvdXQgPDwgbCA8PCAiICIgPDwgciA8PCBlbmRsOyAKCWZvcihpbnQgaSA9IDEsIGogPSAwOyBpIDw9IHI7IGkrKyl7CgkJd2hpbGUoaiA8IHIgJiYgaiA8IGkpewoJCQlpZih2ZWNbaV0gPCB2ZWNbal0pIGFuczErKzsKCQkJaisrOwoJCX0KCQkKCX0KCWlucGxhY2VfbWVyZ2UodmVjLmJlZ2luKCkgKyBsLCB2ZWMuYmVnaW4oKSArIG1pZCwgdmVjLmJlZ2luKCkgKyByKTsKCXJldHVybiBhbnMxOyAKCgkKCQp9CnNpZ25lZCBtYWluKCl7CgkKCWNpbiA+PiBuOwoJZm9yKGludCBpID0gMDsgaSA8IG47IGkrKyl7CgkJaW50IG51bTsgCgkJY2luID4+IG51bTsKCQl2ZWMucHVzaF9iYWNrKG51bSk7Cgl9Cgljb3V0IDw8IHJlY3VyKDAsIG4pIDw8IGVuZGw7IAp9

MTAKMSA1IDYgOSA4IDcgMTAgMiA0IDMK

10
1 5 6 9 8 7 10 2 4 3