crescator

Time limit: 0.3s Memory limit: 128MB Input: crescator.in Output: crescator.out

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

Subsecvența [l,r][l, r] a șirului bb este șirul bl,bl+1,bl+2,,brb_l, b_{l+1}, b_{l+2}, \dots, b_r.

Cerință

Se dă NN și un șir a1,a2,a3,,aNa_1, a_2, a_3, \dots, a_N. Se dau QQ interogări de forma [l,r][l, r] spuneți dacă subsecvența [l,r][l, r] este sortată crescător (alal+1al+2ara_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 NN. Pe a doua linie se află șirul a1,a2,,aNa_1, a_2, \dots, a_N.
Pe a treia linie se află numărul QQ și pe următoarele QQ linii se află perechea l,rl, r.

Date de ieșire

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

Restricții și precizări

  • 1N,Q200 0001 \leq N, Q \leq 200 \ 000
# Punctaj Restricții
1 10 N=2,Q=1,l=1,r=2N = 2, Q = 1, l = 1, r = 2
2 30 N,Q2 000N, Q \leq 2 \ 000
3 60 Fără restricții suplimentare

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][1, 4] este 3,7,8,123, 7, 8, 12 care este sortată crescător.

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

Log in or sign up to be able to send submissions!