Bubble Sort

Time limit

Memory limit

128 MB

Problem

Suppose the following C++ bubble sort code is executed.

cpp

bool changed = false;for (int i = 1; i <= N + 1; i++) {    changed = false;    for (int j = 1; j <= N - i; j++) {        if (A[j] > A[j + 1]) {            changed = true;            swap(A[j], A[j + 1]);        }    }    if (changed == false) {        cout << i << '\n';        break;    }}

bool changed = false;for (int i = 1; i <= N + 1; i++) {    changed = false;    for (int j = 1; j <= N - i; j++) {        if (A[j] > A[j + 1]) {            changed = true;            swap(A[j], A[j + 1]);        }    }    if (changed == false) {        cout << i << '\n';        break;    }}

Here, N is the size of the array, and A is the array to be sorted. The array uses indices from A[1] through A[N].

Determine the value printed when this code is executed.

Input

The first line contains the array size N. N is a positive integer not greater than 500,000.

Each of the next N lines contains one value: A[1], A[2], ..., A[N]. Every value is an integer between 0 and 1,000,000, inclusive.

Output

Print the value that the code outputs.