Masala #R109F

Azizbek yaqinda eng uzun o‘suvchi qism ketma-ketlik (Longest Increasing Subsequence, LIS) mavzusini o‘rgandi.

Butun sonlardan iborat \(A = (a_1, a_2, …, a_k)\) massiv berilgan bo‘lsin. \(A\) ning qism ketma-ketligi deb \(A\) dan ayrim elementlarni o‘chirib tashlash (hech birini o‘chirmaslik ham, hammasini o‘chirish ham mumkin) orqali, qolgan elementlarni dastlabki tartibda qoldirib hosil qilingan ketma-ketlikka aytiladi.

Agar ushbu qism ketma-ketlik elementlari chapdan o‘ngga qat’iy o‘suvchi bo‘lsa \((b_i < b_{i+1}, \  1 \le i < n)\), u A ning o‘suvchi qism ketma-ketligi deyiladi. Elementlari soni eng ko‘p bo‘lgan o‘suvchi qism ketma-ketlik \(A\) ning eng uzun o‘suvchi qism ketma-ketligi hisoblanadi.

Masalan, (2,4,5,6) va (1,4,5,6) ketma-ketliklari (2,1,1,4,7,5,6) massivining eng uzun o‘suvchi qism ketma-ketliklari bo‘lib, ularning uzunligi 4 ga teng.

Endi Azizbek quyidagi savolga duch keldi:
\(B = (b_1, b_2, …, b_m)\) ketma-ketlik berilgan bo‘lsin. \(C\) — \(B\) ning biror qism ketma-ketligi bo‘lsin va \(C\) ning eng uzun o‘suvchi qism ketma-ketligi uzunligi \(k\) dan oshmasin. Shu shart ostida \(C\) ning maksimal uzunligi nechaga teng bo‘lishi mumkin?

Azizbek bu savolni juda oson deb hisoblab, yanada qiyinroq masala o‘ylab topdi. U sizga \(B = (b_1, b_2, …, b_n)\) ketma-ketligini va bir nechta so‘rovlarni beradi. Har bir so‘rovda ikkita butun son \(m\) va \(k\) beriladi. Siz B ketma-ketligining dastlabki m ta elementidan tashkil topgan massiv uchun yuqoridagi savolga javob berishingiz kerak.

Birinchi qatorda ikkita butun son \(n\) va \(q\) beriladi. Bu yerda \(n\) — \(B\) massivining uzunligi, \(q\) — so‘rovlar soni.
Ikkinchi qatorda bo‘shliqlar bilan ajratilgan \(n\) ta musbat butun son \(b_1, b_2, …, b_n\) beriladi.
Keyingi \(q\) qatorda, \(i-\) qatorda ikkita butun son \(m_i\) va \(k_i\) beriladi.

\(1 \le n ≤ 10^5\)

\(1 \le q \le 2 \times 10^5\)

\(1 \le b_i \le n\)

\(1 \le k_i \le m_i \le n\)

Jami q ta qatorda, har bir so‘rov uchun javobni chiqaring.