Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Easy Peasy, Lemon Squeezy 2

By Mehedi_Hassan · Limits 1s, 256 MB

You will be given an array AA of length NN. 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(1N105)N (1\leq N\leq 10^5), the length of the array.

The second line contains NN integers A1,A2,,AN(1Ai105)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

InputOutput
5
3 1 5 1 2
5

    Discussion

    Statistics


    45% Solution Ratio

    TanjumEarliest, 1M ago

    YouKnowWhoFastest, 0.0s

    YouKnowWhoLightest, 524 kB

    u1904103Shortest, 574B

    Submit

    Login to submit

    Editorial

    Prerequisites: Binary Indexed Tree/ Policy Based Data Structure/ Merge sort Explanation: This is a c...