题目背景

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

7
3
1 3 1
2
5 7
3
0 1 0
1
2
6
3 3 2 1 0 0
5
1 3 2 2 3
3
1 0 1

TAK
NIE
TAK
NIE
TAK
NIE
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$。