Description

Looking toward the possibility of a long-term career beyond the farm, the cow Bessie has started studying algorithms on various online programming websites.

Her favorite algorithm so far is "bubble sort." Below is Bessie's initial code implementation 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

Clearly, the moo instruction in the code simply outputs "moo." Strangely, Bessie seems fixated on using this statement in different places in her code.

After testing her code on several arrays, Bessie noticed an interesting phenomenon: large elements are quickly pulled to the end of the array, while small elements take a long time to "bubble" up to the front (she suspects this is why the algorithm has this name). To experiment and ease this issue, Bessie modified her code so that in each loop it scans forward and then backward, giving both large and small elements a chance to move a relatively long distance in each loop. Her code is now as follows:

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 an input array, predict how many times Bessie's modified code will output "moo."

Input Format

The first line contains $N$ ($1 \leq N \leq 100,000$). The next $N$ lines describe $A[0] \ldots A[N-1]$, each an integer in the range $0 \ldots 10^9$. The input numbers are not guaranteed to be distinct.

Output Format

Output the number of times "moo" is printed.

5
1
8
5
3
2

2

Hint

Problem by Brian Dean.

Translated by ChatGPT 5