Masala #3YH2WQ02PM

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.