Out of Sorts (Silver)#10384
Sign in

Out of Sorts (Silver)

1 second
128 megabytes
Medium

Keeping an eye on long-term career opportunities beyond the farm, Bessie the cow has started learning algorithms on various online coding websites.

Her favorite algorithm so far is "bubble sort". Here is Bessie's implementation, in cow-code, for sorting an array of length :

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

Apparently, the "moo" command in cow-code does nothing except print "moo". Strangely, Bessie insists on including it at various places in her code.

Given the input array, predict how many times Bessie's code will print "moo".

Input

The first line contains an integer n~(1 \le n \le 10^5). Each of the next lines contains one element of the array A_0, \ldots, A_{n-1} — an integer from to 10^9. The elements are not necessarily distinct.

Output

Print one integer — the number of times "moo" is printed.

Examples

Example 1

Loading
Loading