Problem description

Jasio ma długi ciąg liczb i zastanawia się, czy niektóre z jego spójnych podciągów są uporządkowane. Jasio jest dziwny i słowo uporządkowany dla niego wcale nie znaczy tyle co posortowany. Jasio nazywa ciąg uporządkowanym, gdy jest on przestawieniem (permutacją) pewnych kolejnych liczb naturalnych.

Na przykład ciągi (4,5,3) oraz (9,8,7) są uporządkowane, ale (3,4,6) i (2,3,2) już nie.

Napisz program, który: wczyta ciąg oraz zapytania Jasia, dla każdego z nich odpowie, czy dany spójny podciąg jest uporządkowany i wypisze wyniki na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N i Q, oddzielone pojedynczym odstępem i oznaczające odpowiednio długość ciągu i liczbę zapytań. W kolejnym wierszu znajduje się N liczb, z których składa się ciąg Jasia: A₁, A₂, …, A_N. W kolejnych Q wierszach znajdują się zapytania, po jednym w wierszu. Każde zapytanie składa się z dwóch liczb naturalnych p_i oraz k_i, oddzielonych pojedynczym odstępem i określających pozycje początku i końca spójnego podciągu, o który pyta Jasio.

Pozycje numerujemy od lewej kolejnymi liczbami naturalnymi od 1 do N włącznie.

Wyjście

Twój program powinien wypisać na wyjście Q wierszy. W i-tym wierszu powinna się znaleźć odpowiedź dla i-tego zapytania Jasia – słowo TAK, jeśli ciąg A_pi, A_pi + 1, …, A_ki jest uporządkowany lub NIE w przeciwnym przypadku.

Ograniczenia

3 ≤ N ≤ 500 000, 1 ≤ Q ≤ 500 000, 1 ≤ A_i ≤ 10⁹.

Przykład

4 3
2 3 2 4
2 4
1 3
1 4

TAK
NIE
NIE