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: A1, A2, …, AN. W kolejnych Q wierszach znajdują się zapytania, po jednym w wierszu. Każde zapytanie składa się z dwóch liczb naturalnych pi oraz ki, 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 Api, Api + 1, …, Aki
jest uporządkowany lub NIE w przeciwnym przypadku.
Ograniczenia
3 ≤ N ≤ 500 000, 1 ≤ Q ≤ 500 000, 1 ≤ Ai ≤ 109.
Przykład
| Wejście | Wyjście | |
|
|