Problem description

Stolica Cesarstwa spłonęła, więc niezwłocznie trzeba zaprojektować miasto na nowo i je odbudować. Pierwszy element projektu jest inicjatywą samego Cesarza – w punkcie centralnym miasta musi powstać pałac, ogromny i przestronny. Twoim zadaniem jest sprawdzenie i ewentualne poprawienie projektu jednej z ulic odchodzących od środka miasta.

Projekt ulicy to ciąg dodatnich liczb całkowitych oznaczających wysokości kolejnych budynków. By pałac był godzien Cesarza, w jego okolicy nie powinno być wysokich budynków, a najlepiej by było, gdyby najbliżej pałacu stały budynki najniższe, a najdalej najwyższe. Innymi słowy projekt ulicy jest dobry wtedy i tylko wtedy, gdy wysokości budynków są posortowane niemalejąco.

Lokalny artysta-architekt przygotował już swoją propozycję projektu, jednak istnieje szansa, że pracując pospiesznie popełnił błąd i wysokości budynków nie są posortowane. By nie urazić uczuć artystycznych lokalnego artysty-architekta, możesz zamienić miejscami co najwyżej jedną parę budynków z projektu.

Czy projekt lokalnego artysty-architekta jest dobry lub czy da się go naprawić jedną zamianą?

Wejście

W pierwszym (jedynym) wierszu wejścia znajduje się jedna dodatnia liczba całkowita N, określająca liczbę budynków w projekcie. W drugim wierszu wejścia znajduje się N dodatnich liczb całkowitych H₁, H₂, …, H_N pooddzielanych pojedynczymi odstępami i określających wysokości kolejnych budynków w projekcie.

Wyjście

Jeżeli projekt jest dobry, to wypisz wyłącznie słowo TAK.

Jeżeli projekt nie jest dobry, ale można go naprawić jedną zamianą budynków, to w pierwszym wierszu wyjścia wypisz słowo NAPRAWA, a w drugim wierszu wyjścia dwie dodatnie liczby całkowite określające pozycje do zamienienia. Pierwsza z wypisanych liczb musi być mniejsza od drugiej.

Jeżeli projekt nie jest dobry i nie da się go naprawić jedną zamianą, to wypisz wyłącznie słowo NIE.

Ograniczenia

1 ≤ N ≤ 500 000, 1 ≤ H_i ≤ 10¹⁸.

Przykład

4
2 5 19 23

TAK

6
3 2 2 1 4 4

NAPRAWA
1 4

5
100 39 42 21 3

NIE