Quickish Sort Work Counter

Bessie created a hybrid sorting algorithm called quickish_sort which combines elements of bubble sort and quick sort. Given an array \( A \) of length \( N \), a position between \( A[i] \) and \( A[i+1] \) is defined as a partition point if

\( \max(A[0\ldots i]) \leq \min(A[i+1\ldots N-1]) \)

The algorithm works as follows:

1. If the array length is 1, return immediately.
2. Otherwise, repeatedly perform a bubble_sort_pass on the array until at least one partition point exists. In one bubble_sort_pass, for each index \( i \) from 0 to \( N-2 \), if \( A[i] > A[i+1] \) then swap these two elements. Each pass increases a global work counter by \( N \) (i.e. work_counter += \( N \)).
3. When one or more partition points exist, divide the array at every partition point. That is, if a partition point exists between \( A[i] \) and \( A[i+1] \), the array is split into segments \( A[0\ldots i] \) and \( A[i+1\ldots N-1] \). Then, recursively apply quickish_sort on each segment (if the segment length is more than one).

Your task is to compute the final value of work_counter after quickish_sort finishes processing the given array.

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[0], A[1], \ldots, A[N-1] \).

outputFormat

Output a single integer representing the final value of work_counter after the algorithm finishes.

sample

3
2 1 3

2