Little Bytie really enjoys watching Formula One races which are held annually on a track between Bytetown and Byteburg. The most exciting moments for him are overtakes. He would like to see as many of them as possible.
Bytie is dreaming of a race in which
Formula One cars compete
and the car that started the race at the
-th position (for each
)
performs
overtakes during the race.
We assume for simplicity that at each moment of time at most one overtaking takes place,
in which exactly two cars participate (that is, one car goes past another car).
Bytie is wondering whether such a race is possible at all. Could you help him figure this out?
The first line of input contains one positive integer
that represents
the number of test cases that follow.
Each test case is described in two lines.
The first line contains one integer
(
): the number of cars that participate in the race.
The second line holds a sequence of
integers
(
) that gives the number of overtakes performed by
the respective cars.
The size of a single input file does not exceed 20MB.
Your program should output
lines containing answers to the respective test cases.
Each line should hold a single word TAK (Polish for yes)
or NIE (Polish for no) depending on whether the race described
by the test case is possible or not.
For the input data:
3 2 0 1 3 0 1 4 3 1 1 3
the correct result is:
TAK NIE TAK
Task author: Tomasz Idziaszek.
W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem szkopul@fri.edu.pl.
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, odwiedź nasze serwery na Discordzie. Są one moderowane przez społeczność, ale członkowie zespołu wsparcia również aktywnie się tam udzielają.