P11917 [PA 2025] 点兵点将 / Wyliczanka

PA 2025 R2B.

有 $n$ 个玩具，编号 $1\sim n$，现在要点兵点将。流程如下： 1. 选择一个 $1\le i\le n$，然后指着玩具 $i$ 。 2. 选择是否终止点兵点将； 3. 如果不终止，设当前指着的玩具是 $j$。 - 若 $j=1$，转而指着 $j+1$，然后回到 2； - 若 $j=n$，转而指着 $j-1$，然后回到 2； - 否则，选择转而指着 $j+1$ 或 $j-1$，然后回到 2。 将每个玩具被指着的次数（包括步骤 1 的一次）记录下来，可以得到一个序列。我们说这个游戏**生成**了这个序列。 给定一个长度为 $n$ 的非负整数序列 $a_1,a_2,\ldots,a_n$。判断是否存在一个合法的游戏生成序列 $a$。

**本题单个测试点内有多组测试数据。** 第一行，正整数 $T$，表示测试数据组数。 接下来依次描述 $T$ 组数据： 每组数据第一行，正整数 $n$。 每组数据第二行，$n$ 个非负整数 $a_1,a_2,\ldots,a_n$。 保证每组数据存在一个非零的 $a_i$。

每组数据输出一行： - 若存在一个游戏生成序列，输出 $\texttt{TAK}$； - 否则输出 $\texttt{NIE}$。

### 样例解释 - 样例 $1$ 解释：依次指着 $2,1,2,3,2$ 即可。 - 样例 $3$ 解释：指着 $1$ 后终止游戏即可。 - 样例 $5$ 解释：依次指着 $1,2,3,4,3,2,1,2,1$ 即可。 ### 数据范围 - $1\le T\le 10^5$； - $1\le n,\sum n\le 10^6$； - $ 0 \leq a_i \leq 10^9 $； - 每组数据中，至少有一个非零的 $a_i$。