Bubble Sort

Bubble sort repeatedly compares two adjacent values in an array and swaps them when the left value is greater than the right value. An integer array A[0], A[1], ..., A[N-1] contains N distinct integers. To sort A in ascending order, Taeguk wrote the following code.

for (i=0; i<N; i++) {
    flag = 0;
    for (j=0; j<N-1; j++) {
        if (A[j] > A[j+1]) {
            flag = 1;
            temp = A[j];
            A[j] = A[j+1];
            A[j+1] = temp;
        }
    }
}

Depending on the input array, however, the array may become sorted before variable i finishes every iteration. Dohyun improved the code so that it stops as soon as one full outer iteration performs no swaps.

for (i=0; i<N; i++) {
    flag = 0;
    for (j=0; j<N-1; j++) {
        if (A[j] > A[j+1]) {
            flag = 1;
            temp = A[j];
            A[j] = A[j+1];
            A[j+1] = temp;
        }
    }
    if (flag == 0) {
        break;
    }
}

Given array A, determine the value stored in variable i at the moment the improved code finishes sorting and leaves the outer for loop.

The first line contains an integer N (1 <= N <= 500,000).

The second line contains the N integers of array A in order, separated by spaces. All given integers are distinct, and the absolute value of each integer does not exceed 2,147,483,647.

Print the value stored in variable i when sorting is complete and the outer for loop is left.