【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$ 的排列。