Bubble Sort

Time limit2sMemory limit128 MB

Summary

Given an array, compute how many bubble sort passes occur before no swaps happen, without simulating the O(N^2) sort directly for N up to 500,000.

Level: Medium7 of 10
Topics: Sorting, Segment tree, Greedy, Array
Solved: No attempts yet

Problem

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

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.

Examples2

Example 1
Input
```
5
10
1
5
2
3
```
Expected output
```
3
```
Example 2
Input
```
5
1
3
5
7
9
```
Expected output
```
1
```