Masala #3YH2WQ02PM

Xotira 256 MB Vaqt 2000 ms
14

O'suvchi qism ketma-ketlik

Ahmadjonda uzunligi \(n\) bo'lgan \(p\) permutatsiya* bor. U \(1 \leq i_1 \leq i_2 \leq \dots i_k \leq n\) ketma-ketlikni sekin o'suvchi deydi, agarda har bir \(1 \leq j < k\) uchun \(p_{i_j} + 1 = p_{i_{j+1}}\) sharti bajarilsa.

Boshqa so'z bilan aytgancha, \(p_{i_1},p_{i_2},\dots p_{i_k}\) ketma-ketlik, \(x, x + 1, \dots x + k-1\) shaklidagi ketma ket sonlardan tashkil topsin.

Qodirjon Ahmadjonga \(q\) ta \((l, r)\) turdagi so'rovlarni beradi. Har so'rovga Ahmadjon \(p\) massivining \([l, r]\) oralig'idagi eng uzun sekin o'suvchi ketma-ketlikning uzunligini aytishi lozim. Ahmadjonga yordam bering.

*Permutatsiya bu 1 dan \(n\) gacha sonlarning har biri 1 martadan qatnashgan massivdir.


Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita butun son - \(n, q(1 \leq n, q \leq 2*10^5)\) sonlari kiritiladi.

Ikkinchi qatorda \(n\) ta butun son - \(p\) permutatsiya elementlari kiritiladi.

Uchunchi qatordan boshlab har so'rov uchun yangi qatorda \(l,r(1 \leq l \leq r \leq n)\) sonlari kiritiladi.


Chiquvchi ma'lumotlar:

Har bir so'rov uchun alohida qatorda, \([l, r]\) oraliqdagi eng uzun sekin o'suvchi ketma-ketlikning uzunligini toping.


Misollar
# input.txt output.txt
1
7 3
1 5 2 6 4 7 3
1 3
1 6
3 7
2
3
2