Masala #33X3AU6PZL

Xotira 256 MB Vaqt 1500 ms

Qat'iy o'suvchi oraliqlar

Uzunligi \(N\) ga teng bo'lgan\(A\) massivi berilgan. \([L, R]\) oraliqqa yoqimtoy oraliq deyiladi, agarda shu oraliqdan tashkil qilgan massiv qat'iy o'suvchi hisoblansa. Boshqa so'zlar bilan aytganda \(A_l < A_{l+1} < ... < A_r\) sharti bajarilishi lozim.

Bundan tashqari \(Q\) ta so'rov mavjud, har bir so'rov uchun \(x\) va \(y\) sonlari kiritiladi. Bundan so'ng massivdagi \(x\)-element \(y\) soniga o'zgaritirladi. Ya'ni \(A_x \leftarrow y\) o'rnatiladi.

Kiruvchi ma'lumotlar:

\(N\) va \(Q\) kiritiladi \((1 \le N, Q \le 2 * 10^5)\).

Keyingi qatorda N ta butun son - A massiv elementlari kiritiladi \((1 \le A_i \le 10^9)\).

Keyingi Q ta qatorning har birida ikkitadan butun son x va y kiritiladi.

Subtask #1: \(N, Q \le 80\) (10 ball)
Subtask #2: \(N, Q \le 500\) (20 ball)
Subtask #3: \(N, Q \le 5000\) (30 ball)
Subtask #4: Qo'shimcha cheklovlarsiz (40 ball)

Chiquvchi ma'lumotlar:

Keyingi \(Q\) ta qatorda har bir so'rovdan so'ng massivdagi qat'iy o'suvchi oraliqlar sonini chop eting.

Misollar

#	input.txt	output.txt
1	3 100 10 2 2 3 1 2 1000	3 4
2	8 13 10 14 4 20 6 9 16 5 2 3 2 10 1 5 3 15 2 5	13 13 15 15 13

Izoh:

1-test 1-subtaskning 1-testiga to'g'ri keladi.

2-test 1-subtaskning 2-testiga to'g'ri keladi.

4-subtaskning 1-test: \(A_i = i\), \(Q = 1\), \(x_1 = 1\),\(y_1 = 1\)