Masala #3YH2WQ02PM
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.
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.
Har bir so'rov uchun alohida qatorda, \([l, r]\) oraliqdagi eng uzun sekin o'suvchi ketma-ketlikning uzunligini toping.
# | input.txt | output.txt |
---|---|---|
1 |
7 3 1 5 2 6 4 7 3 1 3 1 6 3 7 |
2 3 2 |