Simulation - Concursul Național de Informatică 2024 | crescator

Un șir $b_1, b_2, \dots, b_k$ se numește crescător dacă și numai dacă $b_1 \leq b_2 \leq b_3 \leq \dots \leq b_{k-1} \leq b_k$.

Subsecvența $[l, r]$ a șirului $b$ este șirul $b_l, b_{l+1}, b_{l+2}, \dots, b_r$.

Cerință

Se dă $N$ și un șir $a_1, a_2, a_3, \dots, a_N$. Se dau $Q$ interogări de forma $[l, r]$ spuneți dacă subsecvența $[l, r]$ este sortată crescător ($a_l \leq a_{l+1} \leq a_{l+2} \leq \dots \leq a_r$).

Date de intrare

Pe prima linie a fișierului de intrare crescator.in se află numărul $N$. Pe a doua linie se află șirul $a_1, a_2, \dots, a_N$.
Pe a treia linie se află numărul $Q$ și pe următoarele $Q$ linii se află perechea $l, r$.

Date de ieșire

Să se afișeze în fișierul crescator.out se afișează $Q$ linii. A $i$-a linie este DA dacă răspunsul la a $i$-a întrebare este da, și NU altfel.

Restricții și precizări

• $1 \leq N, Q \leq 200 \ 000$

Exemplu

crescator.in

10
3 7 8 12 4 2 5 5 1 8
7
1 4
2 4
3 5
5 6
6 8
6 9
1 10

crescator.out

DA
DA
NU
NU
DA
NU
NU

Explicație

La prima întrebare răspunsul este DA, deoarece subsecvența $[1, 4]$ este $3, 7, 8, 12$ care este sortată crescător.

La a treia întrebare, răspunsul este NU, deoarece subsecventa $[3, 5]$ este $8, 12, 4$ care nu e sortată crescător ($12 > 4$).