【MX-J2-T4】Turtle and Cycles
题目描述
给你一个环形的 $0 \sim n - 1$ 的**排列** $a_0, a_1, \ldots, a_{n - 1}$。
一次操作你可以选择一个整数 $i \in [0, n - 1]$,把 $a_i$ 赋值成 $a_{(i - 1) \bmod n} + a_{(i + 1) \bmod n} - a_i$。
一个位置 $i \in [0, n - 1]$ 是好的当且仅当 $a_{(i - 1) \bmod n} < a_i$ 且 $a_{(i + 1) \bmod n} < a_i$。
环形序列 $a$ 是好的当且仅当存在**恰好**一个位置 $i \in [0, n - 1]$ 使得位置 $i$ 是好的。
求至少要进行多少次操作能让 $a$ 变成好的。可以证明一定有解。
输入输出格式
输入格式
**本题有多组测试数据。**
第一行输入一个正整数 $T$,表示测试数据组数。
对于每组测试数据:
第一行包含一个正整数 $n$。
第二行包含 $n$ 个非负整数 $a_0, a_1, \ldots, a_{n - 1}$。
输出格式
对于每组数据,输出一行一个整数,表示最少要进行的操作次数。
输入输出样例
输入样例 #1
3
2
1 0
5
2 3 0 4 1
10
0 5 9 7 3 1 6 4 8 2
输出样例 #1
0
1
5
说明
#### 【样例解释】
在第一组数据中,初始序列恰好存在一个好的位置 $i = 0$,所以答案为 $0$。
在第二组数据中,可以选择 $i = 2$ 操作,操作后序列变为 $a = [2, 3, 7, 4, 1]$。此时序列恰好存在一个好的位置 $i = 2$,所以答案为 $1$。
#### 【数据范围】
**本题采用捆绑测试且开启子任务依赖。**
| 子任务编号 | 分值 | $n \le$ | $\sum n \le$ | 特殊性质 | 子任务依赖 |
| :-: | :-: | :-: | :-: | :-: | :-: |
| $1$ | $19$ | $6$ | $10^4$ | 无 | 无 |
| $2$ | $14$ | $12$ | $10^4$ | 无 | $1$ |
| $3$ | $27$ | $2 \cdot 10^3$ | $10^4$ | 无 | $1, 2$ |
| $4$ | $2$ | $2 \cdot 10^5$ | $2 \cdot 10^5$ | $a_i = i$ | 无 |
| $5$ | $38$ | $2 \cdot 10^5$ | $2 \cdot 10^5$ | 无 | $1, 2, 3, 4$ |
对于所有数据,满足 $1 \le T \le 10^4$,$2 \le n, \sum n \le 2 \cdot 10^5$,$0 \le a_i \le n - 1$,$a$ 是一个 $0 \sim n - 1$ 的排列。