Background

Original link: https://oier.team/problems/J2E.

Problem Description

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.

Input Format

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}$.

Output Format

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

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

0
1
5

Hint

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.

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