题目描述

给你一个环形的 $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}$。

输出格式

对于每组数据，输出一行一个整数，表示最少要进行的操作次数。

3
2
1 0
5
2 3 0 4 1
10
0 5 9 7 3 1 6 4 8 2

0
1
5

提示

【样例解释】

在第一组数据中，初始序列恰好存在一个好的位置 $i = 0$，所以答案为 $0$。

在第二组数据中，可以选择 $i = 2$ 操作，操作后序列变为 $a = [2, 3, 7, 4, 1]$。此时序列恰好存在一个好的位置 $i = 2$，所以答案为 $1$。

【数据范围】

本题采用捆绑测试且开启子任务依赖。

对于所有数据，满足 $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$ 的排列。