Description

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

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 values are not guaranteed to be distinct.

Output Format

Output the number of times 'moo' is printed.

5
1
5
3
8
2

4

Hint

Setter: Brian Dean.

Translated by ChatGPT 5