Modified Bubble Sort Moo Count

Bessie, aspiring to a long-term career beyond the farm, has been studying algorithms on various online coding platforms. Her current favorite is Bubble Sort. Initially, she wrote a simple bubble sort algorithm for an array \( A \) of length \( N \) that printed "moo" in each pass:

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]

However, Bessie noticed that while large elements quickly "bubble" to the end, small elements take a long time to reach the beginning. To mitigate this, she modified her algorithm to perform a forward pass, then a backward pass, and finally check if the array is sorted. The modified algorithm is 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

Your task is: Given an input array, determine how many times the string "moo" is printed when Bessie's modified bubble sort algorithm is executed. Each iteration of the while loop prints "moo" exactly once (right at the beginning of the loop).

Note: The algorithm terminates when the array is sorted.

Hint: Simulate the process as described above. On the first iteration, even if the array is already sorted, you must count that iteration.

inputFormat

The first line contains an integer \( N \) (the size of the array).

The second line contains \( N \) space-separated integers representing the elements of the array \( A \).

\( 1 \leq N \leq 10^3 \). Each element of \( A \) is an integer that fits in a 32-bit signed integer.

outputFormat

Output a single integer: the number of times "moo" is printed during the execution of the algorithm.

sample

3
2 1 3

1