Masala #VGWJMGXBRG
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 ga teng bo’lgan massivi bor. Shuningdek, Qta so’rovda sizga va sonlari beriladi. Vazifangiz 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
Birinchi qatorda sizga N va Q sonlari beriladi - elementlar va so’rovlar soni.
Ikkinchi qatorda - massiv elementlari. Keyingi ta qatorda va - so’rovlar.
Chegaralar
• 1 ≤ ≤ 131 072
• 1 ≤ ≤ 200 000
• , barcha uchun
• 1 ≤ ≤ ≤ , hamda , - nomanfiy butun son
Subtasks
1. (6 ball) So’rovlarda = + 1
2. (13 ball) ≤ 8; = 1; = 1; = N
3. (21 ball) = 1; = 1; = N
4. (24 ball) Barcha so’rovlar uchun javob 2dan oshmaydi.
5. (15 ball) ≤ 16384
6. (21 ball) Qo’shimcha chegaralarsiz.
ta qatorda har bir so’rov uchun javobni chiqaring.
# | 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 |