Figures

Interview

Time limit1sMemory limit128 MB

Summary

Check whether any three consecutive figures contain one circle, one square, and one triangle.

Level: Easy1 of 10
Topics: Sliding window, Array
Solved: No attempts yet

Problem

Jaś drew some figures in his notebook: circles, squares, and triangles, all in a single straight row. After finishing, he lent the notebook to Małgosia, who sits next to him.

Małgosia wants to find three different figures (a circle, a square, and a triangle), in any order, sitting right next to each other. Determine whether she can find such three different figures placed side by side.

Input

The first line contains a single integer $n$ ( $3 \le n \le 10^6$ ), the number of figures Jaś drew.

The second line contains $n$ integers $f_1, f_2, \dots, f_n$ ( $0 \le f_i \le 2$ ) describing the figures in order. $f_i$ denotes the $i$ -th figure: 0 is a circle, 1 is a square, and 2 is a triangle.

Output

Print a single word TAK if Małgosia can find three different figures next to each other, or NIE otherwise.

Examples1

Example 1
Input
```
7
2 2 1 2 1 0 1
```
Expected output
```
TAK
```