BS-M7. Birinchi «katta yoki teng»

O‘sish tartibidagi massiv va q ta so‘rov berilgan. Har so‘rovda son x: massivning x dan kichik bo‘lmagan (aᵢ ≥ x) birinchi elementi qaysi o‘rinda turibdi? O‘rinlar 1 dan sanaladi. Bunday element bo‘lmasa, n + 1 chiqaring.

Bu — binar qidiruvning asosiy savoli («lower bound»): keyingi ko‘p masalalar shunga tayanadi.

Kirish ma’lumotlari

Birinchi qatorda n, ikkinchisida o‘sish tartibida (kamaymaydigan) n ta butun son. Uchinchi qatorda q, to‘rtinchisida q ta so‘rov — butun sonlar x.

Chiqish ma’lumotlari

Har so‘rovga alohida qatorda o‘rin (1 dan n + 1 gacha).

Cheklovlar

1 ≤ n, q ≤ 2·10⁵; sonlar modul bo‘yicha 10⁹ dan oshmaydi.