P10843 [MX-J2-T4] Turtle and Cycles

Original link: .

You are given a circular **permutation** $a_0, a_1, \ldots, a_{n - 1}$ of $0 \sim n - 1$. In one operation, you may choose an integer $i \in [0, n - 1]$ and set $a_i$ to $a_{(i - 1) \bmod n} + a_{(i + 1) \bmod n} - a_i$. A position $i \in [0, n - 1]$ is good if and only if $a_{(i - 1) \bmod n} < a_i$ and $a_{(i + 1) \bmod n} < a_i$. The circular sequence $a$ is good if and only if there exists **exactly** one position $i \in [0, n - 1]$ such that position $i$ is good. Find the minimum number of operations needed to make $a$ good. It can be proven that a solution always exists.

**This problem has multiple test cases.** The first line contains a positive integer $T$, the number of test cases. For each test case: The first line contains a positive integer $n$. The second line contains $n$ non-negative integers $a_0, a_1, \ldots, a_{n - 1}$.

For each test case, output one line containing one integer, the minimum number of operations.

#### Sample Explanation In the first test case, the initial sequence has exactly one good position $i = 0$, so the answer is $0$. In the second test case, you can choose $i = 2$ to perform an operation. After the operation, the sequence becomes $a = [2, 3, 7, 4, 1]$. Now the sequence has exactly one good position $i = 2$, so the answer is $1$. #### Constraints **This problem uses bundled testdata and enables subtask dependencies.** | Subtask ID | Score | $n \le$ | $\sum n \le$ | Special Property | Dependency | | :-: | :-: | :-: | :-: | :-: | :-: | | $1$ | $19$ | $6$ | $10^4$ | None | None | | $2$ | $14$ | $12$ | $10^4$ | None | $1$ | | $3$ | $27$ | $2 \cdot 10^3$ | $10^4$ | None | $1, 2$ | | $4$ | $2$ | $2 \cdot 10^5$ | $2 \cdot 10^5$ | $a_i = i$ | None | | $5$ | $38$ | $2 \cdot 10^5$ | $2 \cdot 10^5$ | None | $1, 2, 3, 4$ | For all testdata, it holds that $1 \le T \le 10^4$, $2 \le n, \sum n \le 2 \cdot 10^5$, $0 \le a_i \le n - 1$, and $a$ is a permutation of $0 \sim n - 1$. Translated by ChatGPT 5