Se dă șirul a1, a2, …, an care este o permutare a mulțimii {1, 2, ..., n}. O inversiune în permutare este o pereche (i, j) cu proprietatea că i < j și a[i] > a[j].

Cerința

Să se determine numărul inversiunilor permutării.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații, reprezentând permutarea.

Date de ieșire

Programul va afișa pe ecran numărul S, reprezentând numărul inversiunilor permutării.

Restricții și precizări

• 1 ≤ n ≤ 100.000

Exemplu

Intrare

5
4 2 5 1 3

Ieșire

6

Explicație

Cele 6 inversiuni sunt date de perechile de indici (1,2), (1,4), (1,5), (2,4), (3,4), (3,5).

#include <bits/stdc++.h>


using namespace std;

using PII = pair<int, int>;
using VP  = vector<PII>;
int aib[110011], n, x;
long long int s;

inline void Update(int poz)
{
    for (int i = poz; i <= n; i += i & -i)
        ++aib[i];
}

inline int Query(int poz)
{
    int sum = 0;
    for (int i = poz; i > 0; i -= i & -i)
        sum += aib[i];
    return sum;
}

int main()
{
    cin >> n;
    VP v(n + 1);
    for (int i = 1; i <= n; ++i)
    {
        cin >> x;
        v[i] = {x, i};
    }
    sort(v.begin() + 1, v.end(), greater<PII>());
    for (int i = 1; i <= n; ++i)
    {
        s = (s + Query(v[i].second));
        Update(v[i].second);
    }
    cout << s;
    return 0;
}