Masala E

Tasavvur qiling, siz ulkan bir o‘rmonda sayr qilmoqdasiz! Bu o‘rmonning yo‘lagi bo‘ylab \(N\) ta daraxt saf tortib turibdi. Ularning balandligi har xil bo‘lib, 1 dan \(N\) gacha barcha sonlar ishtirok etgancha har biri o‘ziga xos – ya’ni, bu raqamlar o‘zaro takrorlanmaydigan permutatsiyani hosil qiladi.

Shohruh ushbu o‘rmondan yog‘och yig‘ishga qaror qildi va daraxtlarni kesishda sizning zukkoligingizga suyanmoqda. U quyidagicha kesish usulini o‘ylab topdi: har safar yo‘ldan ketma-ket \(M\) ta daraxt tanlab, ularning barchasining balandligini o‘sha oralig‘idagi eng past daraxt balandligigacha pasaytirib chiqadi. Bu harakatni Shohruh istagancha ko‘p bajara oladi.

Endi esa, Shohruh sizga \(Q\) ta qiziqarli savol beradi! Har bir savolda sizga \(M\) va \(K\) qiymatlari beriladi, va maqsad – siz kesishlar yordamida aynan balandligi \(K\) bo‘lib qolgan daraxtlarning maksimal sonini topishingiz kerak.

Shohruhning barcha savollariga chaqqon va samarali javob bera olasizmi?
 

!! Har bir so'rov oldingisiga bog'liq emas.

Birinchi qatorda \(N\) va \(Q\) beriladi. Ikkinchi qatorda \(N\) ta son, daraxtlar balandligi \(h[1], h[2], \dots, h[N]\) beriladi. Keyingi \(Q\) qatorda har bir so‘rov uchun \(M\) va \(K\) beriladi. Har bir so‘rov uchun alohida qatorda javob chiqaring.
\(N\) — daraxtlar soni.
\(h[i]\) — \(i\)-chi daraxt balandligi.
\(Q\) — so‘rovlar soni.
\(M\) va \(K\) — har bir so‘rov parametrlari.
\(1 \le N,Q \le 10^5\)

\(1 \le M,K \le N\)

Har bir so'rov uchun masala javobini chiqaring.