CodeForces - 61E Enemy is weak

Description
The Romans have attacked again. This time they are much more than the Persians but Shapur is ready to defeat them. He says: "A lion is never afraid of a hundred sheep".
Nevertheless Shapur has to find weaknesses in the Roman army to defeat them. So he gives the army a weakness number.
In Shapur's opinion the weakness of an army is equal to the number of triplets i, j, k such that i < j < k and ai > aj > ak where ax is the power of man standing at position x. The Roman army has one special trait — powers of all the people in it are distinct.
Help Shapur find out how weak the Romans are.
Input
The first line of input contains a single number n (3 ≤ n ≤ 106) — the number of men in Roman army. Next line contains n different positive integers ai (1 ≤ i ≤ n, 1 ≤ ai ≤ 109) — powers of men in the Roman army.
Output
A single integer number, the weakness of the Roman army.
Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cout (also you may use %I64d).
Sample Input
Input

3
3 2 1

Output

1

Input

3
2 3 1

Output

0

Input

4
10 8 3 1

Output

4

Input

4
1 5 4 3

Output

1

제목: 만족을 구하는 세 개의 수는 아래에 표시된 i a[j]> a[k]의 개수이다.
사고방식: 모든 수에 대해 우리는 그것보다 큰 수를 찾고 뒤로 그것보다 작은 수를 찾으며 곱하면 이 수의 결과를 얻을 수 있다. 그리고 모든 수의 가능성을 통계한다. 수량이 너무 많기 때문에 우리는 통합 알고리즘을 사용하여 처리할 때 계산한다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;

struct Node {
	ll val, front, rear;
} a[maxn], b[maxn];
ll ans;

void merge_sort(Node *A, int x, int y, Node *T) {
	if (y - x > 1) {
		int m = x + (y -x) / 2;
		int p = x, q = m, i = x;
		merge_sort(A, x, m, T);
		merge_sort(A, m, y, T);
		while (p < m || q < y) {
			if (q >= y || (p < m && A[p].val <= A[q].val)) {
				ans += A[p].front * (q - m);
				A[p].rear += (q - m);
				T[i++] = A[p++];
			}
			else {
				ans += A[q].rear * (m - p);
				A[q].front += (m - p);
				T[i++] = A[q++];
			}
		}
		for (i = x; i < y; i++)
			A[i] = T[i];
	}
}

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%lld", &a[i].val);
	ans = 0;
	merge_sort(a, 0, n, b);
	cout << ans << endl;
	return 0;
}