Sorting
Alice uses the following pseudocode when she needs to sort a permutation of 1 to N in a 1-indexed array:
procedure Sort(list A) defined as:
list less, greater
if length(A) <= 1 then return A
pivot := Afloor((length(A)+1) / 2)
for i := 1 to length(A) do:
Increment(comparison_count)
if Ai < pivot then append Ai to less else if Ai > pivot append Ai to greater
end if
end for
return concatenate(Sort(less), pivot, Sort(greater) )
And now we are interested in the number of comparisons that will be made during the sorting of the given permutation of integers A with the provided code. So, we ask you to find the value of the variable comparison_count after such a sorting.
Input
The first line of input consists of a single integer N. The second line of input contains a permutation of the numbers 1 to N.
Output
Output the number of comparisons on the first and only line of the output.
Limits
For all testcases
Subtask 1 (32%): 1 ≤ N ≤ 2000
Subtask 2 (9%): 1 ≤ N ≤ 100000, the permutation is generated randomly
Subtask 3 (45%): 1 ≤ N ≤ 65536
Subtask 4 (14%): No additional constraints
Subtask 5 (0%): Sample
Sample Input
5
4 3 5 1 2
Sample Output
11