Byteman 正在组织一场定向越野比赛。参赛者将获得一张标有检查点的地图，他们需要按给定的顺序访问每一个检查点。根据 Byteland 的传统，路线必须是一个闭合的环。目前已经选定了一块合适的区域并规划好了路线。然而，作为起点（也是第一个和最后一个访问的地点）以及比赛方向尚未确定。

Byteman 决定，比赛的每一段路程的难度都不能超过前一段。他走完了全程，并记录了每两个相邻检查点之间的路段难度，用正整数表示。数字越大，对应的路段难度越高。你的任务是检查是否存在这样的起点和比赛方向，使得 Byteman 的约束条件得到满足。

输入格式

标准输入的第一行包含一个整数 $n$ ($2 \le n \le 100\,000$)，表示路线上的检查点总数。检查点编号从 $1$ 到 $n$。第二行包含一个由 $n$ 个整数组成的序列 $t_i$ ($1 \le t_i \le 1\,000\,000\,000$)，其中第 $i$ 个数字描述了检查点 $i$ 和 $i+1$ 之间的路段难度，但 $t_n$ 表示检查点 $n$ 和 $1$ 之间的路段难度。

输出格式

如果存在满足 Byteman 条件的起点和比赛方向，程序应在标准输出的第一行输出 "TAK"（意为是，不含引号），否则输出 "NIE"（意为否）。

样例

样例输入 1

5
3 8 10 1 3

样例输出 1

TAK

说明

在第一个样例中，Byteman 可以将起点设在第四个检查点（即难度为 10 的路段末尾），参赛者可以从这里出发前往第三个检查点。他们沿途经过的连续路段难度依次为 10, 8, 3, 3 和 1。

第一个样例中的定向越野比赛路线。圆圈内为检查点编号，边旁边的数字代表路线中各路段的难度。图中的箭头展示了有效的起点和比赛方向。