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 și y ≤ 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