P4378 [USACO18OPEN] Out of Sorts S

With an eye on the possibility of a long-term career off the farm, the cow Bessie has started learning algorithms on various online programming sites. Her favorite algorithm so far is bubble sort. This is Bessie's cow-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 ``` Obviously, the 'moo' instruction in the cow-code simply prints 'moo'. Strangely, Bessie seems fixated on using this statement at different places in her code. Given an input array, predict how many times Bessie's code will print '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 values are not guaranteed to be distinct.

Output the number of times 'moo' is printed.

Setter: Brian Dean. Translated by ChatGPT 5