题目描述

A railroad siding consists of two (dead-end) sidetracks 1 and 2.

The siding is entered by track A, and left by track B (see figure below).

There are cars on track A, numbered from to .

They are arranged in such a way that they enter the siding in the order .

The cars are to be transferred to the siding, so that they leave it by track B in the order .

Each car is to be transferred once from track A to one of the sidetracks 1 or 2, and later (possibly after some transfers of the remaining cars) once from that sidetrack to the track B.

The sidetracks are long enough to store even the longest trains, so there is no need to worry about their capacity.

输入格式

The first line of the standard input holds one integer () that denotes the number of cars for transfer.

The second line stores the numbers that are a permutation of (i.e., each belongs to , and all these numbers are unique), separated by single spaces.

输出格式

The first line of the standard output should contain the word TAK (yes in Polish) if there is a way of transferring the cars so that they enter track B in the order , or the word NIE (no in Polish) if it is impossible.

If the answer is TAK, the second line should give, separated by single spaces, the numbers of sidetracks (1 or 2) to which successive cars are moved in a correct transfer.

If there are several ways of making the transfer, choose one arbitrarily.

题目大意

题目描述

译自 POI 2010 Stage 1.「Kolej」

一个铁路包含两个侧线 $1$ 和 $2$ ，左边由 $A$ 进入，右边由 $B$ 出去（如下图所示）。

有 $n$ 个车厢在通道 $A$ 上，编号为 $1$ 到 $n$ ，它们按照 $a_1,a_2,\cdots ,a_n$ 的顺序进入侧线，想要按照 $1,2,\cdots ,n$ 的顺序从通道 $B$ 出去。
他们可以从 $A$ 到 $1$ 或 $2$ ，然后经过一系列转移从 $B$ 出去（不用考虑容量问题）。求是否能够做到，如果可以，请找出一种方案。

输入格式

第一行一个正整数 $n$ 。
第二行 $n$ 个空格隔开的正整数 $a_1,a_2,\cdots a_n$ 。

输出格式

第一行一个字符串，如果能够做到，输出 TAK ，否则输出 NIE 。
若能做到，第二行 $n$ 个空格隔开的正整数，表示每个车厢进入的侧线编号。
如果有多解，输出任意一种。

翻译来自于 LibreOJ。

4
1 3 4 2

TAK
1 1 2 1

提示

对于 $100\%$ 的数据，有 $n \le 1 \times 10^5$。