Bessie's Moo in Bubble Sort

Bessie the cow has decided to explore a career beyond the farm by studying algorithms online. Her current favorite is the 'Bubble Sort' algorithm. She has implemented bubble sort in her own unique style, adding a special moo statement in her code.

The algorithm sorts an array \(A\) of length \(N\) 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]
         sorted = false

Each time the algorithm starts an iteration of the while loop, it prints moo once (due to the moo instruction). Given an input array, your task is to simulate the algorithm and determine how many times moo will be printed.

Note: All mathematical formulas must be formatted using LaTeX.

inputFormat

The first line contains an integer \(N\) (the number of elements in the array). The second line contains \(N\) space-separated integers representing the array \(A\).

outputFormat

Output a single integer denoting the total number of times moo is printed during the execution of Bessie's code.

sample

4
4 3 2 1

4