CF2249C Double-Rift Dial

一个长度为 $n$ 的排列 $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$ 的块。 例如，$S=\{1,2,5,7,8,9\}$ 有 $3$ 个块：$\{1,2\}$，$\{5\}$，以及 $\{7,8,9\}$。 当且仅当对 $q$ 的每个非空前缀，其对应集合 $S$ 的块数都不超过 $2$，这个起始位置 $s$ 被称为“好”的起始位置。 求所有“好”的起始位置的数量。 $^{\text{∗}}$ 一个长度为 $n$ 的排列，是一组 $1$ 到 $n$ 的互不相同的整数按任意顺序组成的数组。例如 $[2,3,1,5,4]$ 是排列，而 $[1,2,2]$ 不是（$2$ 出现两次），$[1,3,4]$ 也不是（$n=3$ 但出现了 $4$）。

每个测试用例包含多组测试数据。第一行包含测试用例数 $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$。

对于每组测试数据，输出一个整数，表示“好”的起始位置的数量。

在第一个测试用例中，只有一个起始位置。其每个非空前缀只包含单个值 $1$，只有一个块。因此该位置为好位置。 在第二个测试用例中，从第 $1$ 个位置读出的前 $3$ 个数，集合为 $\{1,3,5\}$，包含 $3$ 个块。因此第 $1$ 个位置不是好的，其余 $4$ 个起始位置均为好位置。 由 ChatGPT 5 翻译