Adrenaline Rush: Maximum Overtake Sequence

Alice, an avid note-taker at the Adrenaline Rush racing competition, observed the race from the stands. Initially, the cars are arranged in increasing order of their numbers: the car closest to the starting line is numbered \(1\), the second \(2\), and so on, up to \(n\). As the race unfolds, Alice notes down every instance where one car overtakes another (i.e. they swap positions). One intriguing detail is that no car overtakes another more than once.

At the finish line, the final order of the cars is recorded as \(c_1, c_2, \ldots, c_n\), where \(c_1\) is the winner. Given that the starting order was \(1, 2, \ldots, n\), an inversion \(\left(\text{a pair }(i, j)\right)\) occurs if a car with a smaller number ends up behind a car with a larger number in the final ordering. In other words, for any two cars with numbers \(i < j\), if car \(i\) appears after car \(j\) in the final sequence, then these two must have swapped positions (overtaking each other at most one time).

Your task is to determine the longest possible sequence of overtakes that could have been observed during the race. This maximum sequence is equal to the inversion count of the final sequence with respect to the initial order.

Note: The inversion count of the final permutation is the number of pairs \((i, j)\) such that \(i < j\) but car \(i\) appears after car \(j\) in the final ordering.

inputFormat

The first line contains an integer \(n\) (the number of cars). The second line contains \(n\) space-separated integers representing the final order of the cars \(c_1, c_2, \ldots, c_n\).

outputFormat

Output a single integer: the longest possible sequence of overtakes (i.e. the total inversion count).

sample

2
2 1

1