2945. [Poi2000]气垫船
#2945. [Poi2000]气垫船
题目描述
在一个气垫船厂用不同高度方块建造了一个测试轨道。一条完美的轨道，被称做 lollobrigida ，是相邻两个方块的高度不同且连续的三个方块的高度既不是递减也不是递增的轨道。
用更形式的表达，设 _h 1,...,hn_是建造轨道的方块的高度。如果任意1 <= i <= n -2都有满足下面条件：
- h i < h i+1 and h i+1 > h i+2 or
- h i > h i+1 and h i+1 < h i+2,
这样我们便称一条轨道为 lollobrigida 。
例子
我们不可能用下面一组高度的方块来建造lollobrigida：3, 3, 3, 5, 2，因为两个高度为3的方块会相邻或者会出现下列情况：(2,3,5)或者(5,3,2)，这些都是不允许的。
这儿有一个用另一组高度的方块建造的lollobrigida的例子(3, 2, 5, 2, 3, 1)。 我们也可以用这些方块建造其他不同的lollobrigidas。
任务
读入几组数据，对于每一组数据：
- 读入方块的个数和每个方块的高度
- 检查是否能建造lollobrigida
输入格式
第一行有一个正整数d，1 <= d <= 100，表示输入数据的组数。接下来的一行是第一组数据。
在每组数据的第一行有一个正整数n，3 <= n <= 1000000，表示方块的个数。
接下来的 n 行中每行有一个正整数 h 表示一个方块的高度1 <= h <= 109。
接着是下一组数据。
输出格式
应该有 d 行，一个表示一组数据。每一行都有一个单词，第 i 行的单词：
- TAK (波兰语中是的意思)，如果第 i 组数据可以建造lollobrigida
- NIE (波兰语中否的意思)，不可以建造
样例
样例输入
2
5
3
3
3
5
2
6
3
3
1
5
2
2
样例输出
NIE
TAK