Cerința
Șcuțu, elev pe clasa a 10
-a, s-a plictisit să lucreze probleme de clasa a 6
-a. Mygo a văzut că Șcuțu a reușit să obțină 100p
pe problema Munte
de la OJI2014
, însă nu cu o soluție prea inteligentă, așa că îi va pune o provocare. Se dă un vector A
de N
elemente indexat de la 1
. Un vârf este un element A[i]
cu proprietatea că A[i-1] < A[i] > A[i+1]
(1 < i < N
). Mygo îi oferă lui Șcuțu Q
operații de tipul:
• 1 x y
: “Elementul de pe poziția x
ia valoarea y
”.
• 2 x y
: “Având o copie a vectorului A[x...y]
(ceea ce urmează nu va afecta cu nimic vectorul A
), se determină toate vârfurile iar acestea se elimină, procedeul acesta continuă până când nu vor mai exista vârfuri. Se cere să se afișeze câte vârfuri au existat de la început până la final”.
Date de intrare
Fișierul de intrare qmunte.in
conține pe prima linie numerele N
și Q
, pe a 2
-a linie se află N
numere naturale reprezentând elementele vectorului A
. Pe următoarele Q
linii se află operațiile.
Date de ieșire
Fișierul de ieșire qmunte.out
va conține răspunsurile operațiilor de tipul 2, câte unul pe fiecare linie, în ordinea în care acestea apar în fișierul de intrare
Restricții și precizări
1 ≤ N, Q ≤ 100.000
- numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât
1.000.000
- pentru operațiile de tipul
1 1 ≤ x ≤ N
șiy ≤ 1.000.000
- pentru operațiile de tipul
2 1 ≤ x ≤ y ≤ N
- testele sunt generate random.
Exemplu:
qmunte.in
6 5 2 12 3 5 4 2 2 1 5 1 2 5 2 1 5 1 6 3 2 1 6
qmunte.out
2 2 3