Circular Permutation Peak Reduction

You are given a circular permutation of the set \(\{0,1,\ldots,n-1\}\) represented by an array \(a_0, a_1, \ldots, a_{n-1}\). You may perform the following operation any number of times:

Choose an index \(i\) (\(0 \le i < n\)) and update

[ a_i \gets a_{(i-1) \bmod n} + a_{(i+1) \bmod n} - a_i. ]

A position \(i\) is called good if

[ a_{(i-1) \bmod n} < a_i \quad\text{and}\quad a_{(i+1) \bmod n} < a_i. ]

The entire circular sequence is said to be good if there is exactly one good position. It can be proved that it is always possible to achieve a good sequence using a finite number of operations.

Task: Find the minimum number of operations required to transform the given permutation \(a\) into a good circular sequence.

---

Observation and Hints:

• Define the differences \(d_i = a_i - a_{(i-1) \bmod n}\) for \(0 \le i 0\) and \(d_{(i+1) \bmod n} < 0\).
• If you let \(s_i = 1\) when \(d_i > 0\) and \(s_i = 0\) otherwise, then the total number of good positions in the final configuration is exactly the number of indices \(i\) where \(s_i = 1\) and \(s_{(i+1)\bmod n} = 0\).
• The desired configuration has exactly one such occurrence. It turns out that one valid target is to have all the 1's in \(s\) (i.e. the positives in \(d\)) appear consecutively (when viewed in a circular manner). In such an arrangement, there will be exactly one transition from 1 to 0.
• An operation on the original array corresponds to swapping two adjacent entries of \(d\) (and hence their corresponding bits in \(s\)). Thus the problem reduces to grouping all the 1's together by adjacent swaps.
• If you let the positions of 1's in \(s\) be \(p_0, p_1, \ldots, p_{m-1}\) (in increasing order) then grouping them into a contiguous block (cyclically) can be achieved with a number of adjacent swaps equal to the minimum cost of aligning these indices to consecutive positions. One standard method is to use the median. In particular, for any block (possibly wrapping around) with indices \(q_0, q_1, \ldots, q_{m-1}\), if we set the target positions to be \(t, t+1, \ldots, t+m-1\) where \(t = q_{\lfloor m/2 \rfloor} - \lfloor m/2 \rfloor\), then the cost is \(\sum_{j=0}^{m-1} |q_j - (t+j)|\). The minimum cost over all cyclic shifts is your answer.

Note that if the 1's are already consecutive (cyclically), the answer is 0.

inputFormat

The first line contains a single integer \(n\) (\(n \ge 3\)).

The second line contains \(n\) space-separated integers \(a_0, a_1, \ldots, a_{n-1}\), which form a permutation of \(\{0, 1, \ldots, n-1\}\).

outputFormat

Output a single integer: the minimum number of operations required to make the circular sequence good.

sample

3
0 1 2

0

</p>