Masala #VGWJMGXBRG

Xotira 128 MB Vaqt 1500 ms
14

Thanos sort

Tanosning saralash algoritmi deb quyidagi saralashga aytiladi: - Agar massiv kamaymaslik tartibida* saralangan bo’lsa, u holda Tanos hech narsa qilmaydi. - Aks holda Tanos cheksizlik toshlari yordamida massivni teng ikkiga bo’ladi va istalgan yarmini o’chirib tashlaydi. - Massiv saralanmagunicha shu ishni davom ettiradi.
Sizda uzunligi NN ga teng bo’lgan a[1],a[2],...,a[N]a[1], a[2], ..., a[N ]massivi bor. Shuningdek, Qta so’rovda sizga ll va rrsonlari beriladi. Vazifangiz a[l],a[l+1],...,a[r]a[l], a[l + 1], ..., a[r]qismmassivni saralash uchun cheksizlik toshlarini eng kamida nechi marta ishlatish kerakligini topish. Bunda berilgan qismmassiv uzunligi 2 ning darajasi ekanligi kafolatlanadi.
*Kamaymaslik tartibida har bir element o’zidan avvalgi elementdan kichkina bo’lmasligi lozim.
Ya’ni a[1]a[2]...a[N].a[1] ≤ a[2] ≤ ... ≤ a[N ].


Kiruvchi ma'lumotlar:

Birinchi qatorda sizga N va Q sonlari beriladi - elementlar va so’rovlar soni.
Ikkinchi qatorda a[1],a[2],...,a[N]a[1], a[2], ..., a[N ] - massiv elementlari. Keyingi QQta qatorda ll va rr - so’rovlar.

Chegaralar
      • 1 ≤ NN ≤ 131 072
      • 1 ≤ QQ ≤ 200 000
      • 1  a[i]  1091 ≤   a[i]   ≤ 10^9 , barcha 1 i   N1 ≤  i   ≤  N uchun
      • 1 ≤ ll ≤ rr ≤ NN , hamda rl+1=2xr − l + 1 = 2x , xx - nomanfiy butun son
Subtasks
      1. (6 ball) So’rovlarda rr = ll + 1
      2. (13 ball) NN ≤ 8; QQ = 1; ll = 1; rr = N
      3. (21 ball) QQ = 1; ll = 1; rr = N
      4. (24 ball) Barcha so’rovlar uchun javob 2dan oshmaydi.
      5. (15 ball) NN ≤ 16384
      6. (21 ball) Qo’shimcha chegaralarsiz.


Chiquvchi ma'lumotlar:

QQta qatorda har bir so’rov uchun javobni chiqaring.


Misollar
# input.txt output.txt
1
9 3
3 1 4 1 5 9 2 6 5
1 8
5 5
3 4
2
0
1