Problem description

Bajtek jest naczelnym programistą na niszczycielu należącym do gwiezdnej floty Konfederacji Niezależnych Systemów Operacyjnych. Jednym z jego zadań jest sprawdzanie, czy elektroniczne mózgi maszyn nie zostały uszkodzone podczas walk.

Pierwszym testem, który Bajtek przeprowadza, jest ustawienie robotów w kilka szeregów, jeden za drugim. Następnie porównuje on pozycje zarejestrowane przez maszyny z rzeczywistymi i na tej podstawie ocenia, czy któraś z nich jest wadliwa.

Niestety, po ostatniej bitwie o bitowe rubieże ze złośliwymi robakami, uszkodzeniu uległ system detekcji położenia robotów. Bajtkowi udało się jedynie wydobyć z każdej z maszyn informację o tym, ile jednostek stało na lewo od niej w jej szeregu podczas testu.

Zbliża się czas złożenia Wielkiemu Deklaratorowi raportu z testu. Bajtek postanowił, że w celu uniknięcia nagany za niedziałający system statku, sfinguje ułożenie robotów, tak żeby było one zgodne z tym, co twierdzą maszyny.

Pomóż mu i napisz program, który wypisze TAK, gdy istnieje ułożenie robotów w szeregi zgodne z ich zeznaniami lub NIE w przeciwnym przypadku (wtedy Bajtek będzie musiał przyjrzeć się każdej maszynie z osobna i spróbować wydedukować, która z nich się popsuła, zanim spotka go gniew Wielkiego Deklaratora).

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N, oznaczająca liczbę robotów.
W drugim wierszu wejścia znajduje się N liczb całkowitych l₁, l₂, …, l_N, pooddzielanych pojedynczymi odstępami. Liczba l_i jest równa liczbie maszyn na lewo od i-tego robota w jego szeregu.

Wyjście

Twój program powinien wypisać TAK, jeżeli istnieje ułożenie robotów w szeregi zgodne z opisem lub NIE w przeciwnym przypadku.

Ograniczenia

1 ≤ N ≤ 1 000 000, 0 ≤ l_i < 1 000 000.

Przykłady

6
0 1 2 0 1 0

TAK

###
##
#

9
0 0 0 0 1 1 1 2 2

TAK

###
##
###
#

3
0 0 2

NIE