Out of Sorts

Time limit2sMemory limit512 MB

Summary

Given an array, count how many times the outer loop of a forward-backward bubble sort variant runs before the array becomes sorted.

Level: Hard8 of 10
Topics: Sorting, Math, Implementation, Greedy
Solved: No attempts yet

Problem

Bessie the cow is looking past the farm at longer term career options, so she has started learning algorithms on coding websites.

Her favorite algorithm so far is bubble sort. Here is her first implementation, written in cow-code, for sorting an array $A$ of length $N$ .

sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
         sorted = false

In cow-code the moo command does nothing except print moo. Bessie insists on putting it at various points in her code.

After testing her code on several arrays, Bessie noticed something. A large element is pulled to the end of the array very quickly, while a small element can take a long time to bubble up to the front. She suspects that this is where the algorithm gets its name. To reduce the problem, Bessie rewrote the main loop so that each iteration scans forward and then backward. Now a large element and a small element both get a chance to move a long distance in one iteration. Her code looks like this.

sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
   for i = N-2 downto 0:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         sorted = false

Given the input array, predict how many times Bessie's rewritten code prints moo.

Input

The first line contains $N$ ( $1 \leq N \leq 100000$ ). Each of the next $N$ lines contains one array element, $A_0$ through $A_{N-1}$ , an integer with $0 \leq A_i \leq 10^9$ . The elements are not guaranteed to be distinct.

Output

Print how many times moo is printed.

Examples3

Example 1
Input
```
5
1
8
5
3
2
```
Expected output
```
2
```
Example 2
Input
```
1
0
```
Expected output
```
1
```
Example 3
Input
```
6
1
1
2
2
3
3
```
Expected output
```
1
```