CF2249C.Double-Rift Dial

A permutation$^{\text{∗}}$ $p$ of length $n$ is written clockwise on a circular dial.

Choose a starting position $s$ ($1\le s\le n$) and read one full circle clockwise from $p_s$, wrapping around after $p_n$. The resulting sequence is

q=\[p\_s,p\_{s+1},\\ldots,p\_n,p\_1,\\ldots,p\_{s-1}\],

which also has a length of $n$.

For any non-empty prefix of this sequence $[q_1, q_2, \ldots, q_k]$ ($k\ge 1$), let $S$ be the corresponding set of values, that is, $S={q_1, q_2,\ldots, q_k}$. Split $S$ into maximal segments of consecutive integers, and we call these segments the blocks of $S$.

For example, $S={1,2,5,7,8,9}$ has $3$ blocks: ${1,2}$, ${5}$, and ${7,8,9}$.

A starting position $s$ is called good if and only if, for every non-empty prefix of $q$, the corresponding set $S$ has at most $2$ blocks.

Find the number of good starting positions.

$^{\text{∗}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

一个长度为 $n$ 的排列$^{\text{∗}}$ $p$ 按顺时针方向写在一个圆形表盘上。

选择一个起始位置 $s$（$1\le s\le n$），并从 $p_s$ 开始沿顺时针方向完整读取一圈，即在 $p_n$ 之后循环回到 $p_1$。所得序列为

q=\[p\_s,p\_{s+1},\\ldots,p\_n,p\_1,\\ldots,p\_{s-1}\],

其长度也为 $n$。

对序列 $q$ 的任意非空前缀 $[q_1, q_2, \ldots, q_k]$（$k\ge 1$），令 $S$ 为其对应值的集合，即 $S={q_1, q_2,\ldots, q_k}$。将 $S$ 划分为若干个极大的连续整数段，这些段称为 $S$ 的块（blocks）。

例如，$S={1,2,5,7,8,9}$ 共有 $3$ 个块：${1,2}$、${5}$ 和 ${7,8,9}$。

当且仅当对 $q$ 的每一个非空前缀，其对应集合 $S$ 至多包含 $2$ 个块时，起始位置 $s$ 被称为好位置（good）。

求好位置的个数。

$^{\text{∗}}$ 长度为 $n$ 的排列是指由 $1$ 到 $n$ 中 $n$ 个互不相同的整数以任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（数字 $2$ 在数组中出现两次），$[1,3,4]$ 也不是排列（此时 $n=3$，但数组中出现了 $4$）。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains one integer $n$ ($1\le n\le 2\cdot 10^5$) — the length of $p$.

The second line of each test case contains $n$ integers $p_1,p_2,\ldots,p_n$ ($1\le p_i\le n$, all $p_i$-s are distinct) — the elements of $p$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1\le n\le 2\cdot 10^5$）—— 表示排列 $p$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $p_1,p_2,\ldots,p_n$（$1\le p_i\le n$，且所有 $p_i$ 互不相同）—— 即排列 $p$ 的元素。

保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。

For each test case, print one integer — the number of good starting positions.

对于每个测试用例，输出一个整数——即好起始位置的数量。

In the first test case, there is only one starting position. Every non-empty prefix contains the single value $1$, so it has one block. Thus, this position is good.

In the second test case, after reading the first $3$ numbers from position $1$, the set is ${1,3,5}$ and has $3$ blocks. Thus, position $1$ is not good. Each of the other $4$ positions is good.

在第一个测试用例中，只有一个起始位置。每个非空前缀都只包含单个数值 $1$，因此具有一个块。所以该位置是好的。

在第二个测试用例中，从位置 $1$ 开始读取前 $3$ 个数后，集合为 ${1,3,5}$，具有 $3$ 个块。因此位置 $1$ 不是好的。其余 $4$ 个位置均为好的。