Polish version    English version  
  History of OI -> VII OI 1999/2000 -> Problems


 News
 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
Stage III - results
Stage II - results
Stage I - results
Problems
Regulations
Organization
Hints
Schedule
Stats
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
Niebieskie ksi.eczki
VII Olimpiada Informatyczna 1999/2000

Task: LOL
Author: Piotr Chrz±stowski-Wachtel
Lollobrigida

III stage contest  

A testing track in the factory of hovercrafts is built of standard blocks of different heights. In a perfectly built track, called lollobrigida, there are neither two neighbouring blocks of equal height nor three consecutive blocks with either increasing or decreasing heights.

To express it more formally, let h1,...,hn denote the sequence of heights of blocks belonging to a track. If for each 1 <= i <= n-2 the following conditions are satisfied:

  • hi < hi+1 and hi+1 > hi+2 or
  • hi > hi+1 and hi+1 < hi+2,

then we can call such a track lollobrigida.

Example

One cannot build a lollobrigida with the set of blocks of heights: 3, 3, 3, 5, 2 , because two blocks of height 3 would have to stand side by side or one of the following sequences would have to appear in it : (2, 3, 5) or (5,3,2), and these are not allowed.

Here is an example of a lollobrigida built with another set of blocks - (3, 2, 5, 2, 3, 1). One can build also other lollobrigidas with this set.

Task

Write a program which reads the number of sets of data from the text file LOL.IN and for each set:

  • reads the number of blocks and the height of each block,
  • checks if one can build a lollobrigida with this set,
  • writes the answer to the text file LOL.OUT.

Input

In the first line of the text file LOL.IN there is one integer d, 1 <= d <= 100, equal to the number of sets of data. In the next line of the file LOL.IN the first set of data begins.

In the first line of each set of data there is one integer n, 3 <= n <= 1000000, which is equal to the number of blocks in this set.

In the following n lines there are heights of blocks. Each line contains one integer h equal to the height of the corresponding block, 1 <= h <= 109.

Next sets of data follow one after another.

Output

The text file LOL.OUT should contain exactly d lines, one for each set of data. One word should be written in the i-th line of the file LOL.OUT:

  • TAK (which means YES in Polish), if one can build a lollobrigida, with the i-th set
  • NIE (which means NO in Polish), in the other case.

Example

For the input file LOL.in:

2
5
3
3
3
5
2
6
3
3
1
5
2
2

The correct answer is the output file LOL.OUT

NIE
TAK



Print friendly version