문제

StarMask is another superheroine that you’ve never heard of. As she is a heroine anyway, it is always your pleasure to play a game with her. This time, you are playing a game to sort a permutation of N$N$ numbers. In a permutation, each number from 1 to N$N$ appears exactly once and these are denoted as P[1], …, P[N]$P[1], …, P[N]$. The goal of this game is to sort a given permutation in increasing order using only one exchange rule. The rule is to follow the instructions below sequentially.

1. Choose two numbers i$i$ and j$j$ such that 1 \le i<j \le N$1 \le i<j \le N$.
2. Find the maximum value and minimum value among P[i], P[i + 1], …, P[j - 1], P[j]$P[i], P[i + 1], …, P[j - 1], P[j]$.
3. Exchange these two values.

StarMask knows N$N$ but does not know the permutation. Meanwhile, you know the exact permutation. At the beginning of the game, you announce the inversion of the permutation. The inversion is defined as the number of pairs of (i, j)$(i, j)$ such that 1 \le i < j \le N$1 \le i < j \le N$ and P[i] > P[j]$P[i] > P[j]$. For example, a permutation “2 3 1” has the inversion of 2. As the game goes on, StarMask uses the exchange rule explained above, and you announce the inversion after each exchange rule is executed. Of course, the optimal strategy will be depend on your announcement.
Unfortunately, StarMask’s super power is about physical strength not intellectual brightness and she already made her mind to use which exchange rules even before the game has started. Now, it doesn’t have to be responsive that you are going to make a program to announce the inversion instead of you. That way, you can have fun playing other games with StarMask. But be careful. She will be very mad if your announcement is wrong.