Easy Peasy, Lemon Squeezy 2

You will be given an array $A$ of length $N$. Print the return value of the following function.

int function(int A[], int N) {
    int cnt = 0;

    for(int i = 1; i <= N; i++) {
        int x = A[i];
        int j = i-1;

        while(j >= 1 && A[j] > x) {
            A[j+1] = A[j];
            j--;
            cnt++;
        }

        A[j+1] = x;
    }

    return cnt;
}

Input

First line of input contains an integer $N (1\leq N\leq 10^5)$, the length of the array.

The second line contains $N$ integers $A_1, A_2, …, A_N (1\leq A_i\leq 10^5)$, the elements of the array.

Output

Print the return value of the function.

Sample

5
3 1 5 1 2

5