P4375 [USACO18OPEN] Out of Sorts G

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."

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 the number of times "moo" is printed.

Problem by Brian Dean. Translated by ChatGPT 5