Marsz na orientację [B]

Limit pamięci: 32 MB

Bajtazar organizuje nocny marsz na orientację. Trasa marszu będzie zataczać pętlę długości około pięćdziesięciu kilometrów. Miejsce odbywania się wyścigu jest już znane. Na trasie rozstawiono również punkty kontrolne, które będą zaliczać zawodnicy. Pozostało jedynie wyznaczyć punkt kontrolny, przy którym zlokalizowane będą start i meta zawodów, oraz ustalić kierunek marszu.

Bajtazar przebył całą pętlę i dla każdego odcinka pomiędzy kolejnymi punktami kontrolnymi zanotował jego trudność, określoną liczbą naturalną. Im większa ta liczba, tym trudniejszy odpowiadający jej odcinek. Bajtazar chciałby tak ustalić punkt startowy oraz kierunek marszu, by każdy kolejny odcinek na trasie był nie trudniejszy od poprzedniego. Twoim zadaniem jest napisanie programu, który sprawdzi, czy jest to możliwe.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita (), określająca liczbę punktów kontrolnych na trasie. Punkty kontrolne ponumerowane są kolejno od do . Drugi wiersz zawiera ciąg liczb całkowitych (), w którym -ta liczba określa trudność odcinka pomiędzy punktami kontrolnymi numer oraz , z wyjątkiem , która określa trudność odcinka między punktami i .

Wyjście

Jeśli jest możliwe takie wybranie kierunku marszu oraz pewnego punktu kontrolnego, z którego rozpocznie i przy którym zakończy się marsz, by każdy odcinek przebywany na trasie był nie trudniejszy od poprzedniego, na standardowe wyjście należy wypisać jedno słowo "TAK" (bez cudzysłowów). W przeciwnym przypadku należy wypisać "NIE".

Przykład

Dla danych wejściowych:

5
3 8 10 1 3

poprawną odpowiedzią jest:

TAK

natomiast dla danych wejściowych:

4
5 6 5 6

poprawnym wynikiem jest:

NIE

Wyjaśnienie do przykładu: W pierwszym przypadku Bajtazar może ustawić punkt startowy przy czwartym punkcie kontrolnym (czyli na końcu odcinka o trudności 10) i określić kierunek marszu w stronę trzeciego punktu kontrolnego. Wówczas kolejne odcinki, przez które będzie przebiegać marsz, będą miały trudność 10, 8, 3, 3 i 1. W drugim przypadku żadne ustawienie nie spełnia postawionych przez Bajtazara wymagań.

Ilustracja trasy marszu w pierwszym przykładzie. Liczby umieszczone w kółkach to numery punktów kontrolnych, a liczby przy krawędziach reprezentują trudności odcinków trasy. Strzałki na rysunku określają możliwy punkt startowy oraz kierunek marszu.

Autor zadania: Jakub Łącki.