Rezolvare PBinfo #2534

Bogdan și Ionuț au fost "bff" încă din clasa V, dar acum destinele lor se cam despart…. Pentru a-l consola pe Bogdan, Ionuț i-a făcut o problema cadou. Bogdan nu vrea să-l dezamăgească pe Ionut, așa că vă cere ajutorul pentru a rezolva problema împreuna.

Cerința

Se dă un șir de n elemente, numere naturale. Problema constă în două operații:

1 i val : Elementul de pe poziția i se înlocuiește cu valoarea val.
2 i j : Stabiliți dacă secvența [i,j], din șirul curent, este ordonată crescător.

Date de intrare

Fișierul de intrare bogdan.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații. Pe a treia linie a fișierului se afla numărul O, care reprezintă numărul de operații. Pe următoarele O linii se vor afla operațiile.

Date de ieșire

Fișierul de ieșire bogdan.out va conține răspunsurile pentru operațiile de tipul 2, pe linie nouă fiecare.
Dacă răspunsul este afirmativ, se va afișa DA, în caz contrar NU.

Restricții și precizări

• 1 ≤ n ≤ 100.000
• 1 ≤ O ≤ 300.000
• numerele fiecărui șir curent vor fi mai mici decât 2.000.000.000
• Observație importantă : bff = Best Friends Forever

Exemplu:

bogdan.in

6
22 9 2003 14 8 2003
4
2 1 6
1 1 8
2 1 3
2 4 5

bogdan.out

NU
DA
NU