题目描述

小比特非常喜欢观看一年一度在比特镇和比特堡之间举行的一级方程式赛车比赛。对他来说最激动人心的时刻就是超车。他希望能看到尽可能多的超车。
比特想要一场比赛，其中有 $n$ 辆一级方程式赛车参与比赛，第 i 辆车从第 $i$ 个位置（$1<i<n$）开始比赛，并在比赛中进行 $a_i$ 次超车。我们简化地假设在每个时间点最多只发生一次超车，而且只有两辆车参与（即，一辆车超过另一辆车）。
比特想知道这样的比赛是否可能。你能帮他弄清楚吗？

输入格式

每个输入包含多个测试点。

第一行包含一个正整数 $T$，表示接下来有 $T$ 个测试点。
对于每个测试点：
第一行包含一个整数 $N$ ($1 \le N \le 1000000$)，表示参与比赛的赛车数量。
第二行包含 $N$ 个整数 $A_1,A_2,\ldots,A_n$ ($0 \le A_i \le 10^9$)，表示各辆车的超车次数。

输出格式

请输出 $T$ 行，分别对应各个测试点的答案。
每行应包含一个单词 TAK（表示可以）或 NIE（表示不可以），依据对应测试点的比赛是否可能而定。

输入样例

3
2
0 1
3
0 1 4
3
1 1 3

输出样例

TAK
NIE
TAK

输入样例解释

• 第1个测试点：有2辆车，第2辆车超了1辆车，满足题意，所以输出TAK（可以）。
• 第2个测试点：有3辆车，第3辆车超了4辆车，但是只有3辆车参赛，所以是不可能的，输出NIE（不可以）。
• 第3个测试点：有3辆车，第1辆车超了1辆车，第2辆车超了1辆车，第3辆车超了3辆车，满足题意，所以输出TAK（可以）。