Masala N

Harbiy bazada jangovar tanklar uchun ehtiyot qismlar saqlanadigan uzun ombor bor. Har bir ehtiyot qismning o'z xizmat muddati bor: u qancha katta bo'lsa, shuncha ko'p yurishga yaroqli hisoblanadi.

Tanklar uzoq masofalarga chiqishdan oldin texnik xizmat ko'rish punktiga kiradi. Bu yerda mexanik askar tank uchun kerakli ehtiyot qismlarni ombordan olib keladi. Ayrim ehtiyot qismlar ishlatilgan bo'lsa, ularning xizmat muddati kamayadi. Shu sababli tank uchun mos bo'lgan qismlarni to'g'ri tanlash juda muhim.

Ombordagi ehtiyot qismlar bitta qatorda joylashgan: 1-qism 1-pozitsiyada, 2-qism 2-pozitsiyada va hokazo.

Mexanik:

• bir vaqtning o'zida faqat 1 ta ehtiyot qismni ko'tara oladi;
• bir sekundda 1 pozitsiya yuradi;
• barcha ishlar omborning 0-pozitsiyasida boshlanadi va tugaydi.

2 ta qismni olib kelish uchun ketadigan vaqt:

                     \(𝑡𝑖𝑚𝑒=2×(𝑝1+𝑝2)\)

bu yerda \(p_1\)​ va \(p_2\)​ — tanlangan qismlarning pozitsiyalari.

Bazadagi ta'minot bo'limi boshlig'i mexanikdan ikki xil topshiriq bo'yicha javob so'raydi:

• Savol topshirig'i (t=0): berilgan l qiymat uchun xizmat muddati kamida l bo'lgan 2 ta ehtiyot qismni ombordan olib kelish uchun eng kam necha soniya kerakligini aniqlash. Eng kam vaqt uchun xizmat muddati yetarli bo'lgan eng chapdagi 2 ta qism tanlanadi.
• Buyruq topshirig'i (t=1): xizmat muddati kamida 𝑙 bo'lgan eng chapdagi 2 ta ehtiyot qismni olib kelish, ularning asl xizmat muddatlarini chiqarish, so'ng har birining xizmat muddatini l ga kamaytirish.

Savol topshirig'ida qismlar o'zgarmaydi. Buyruq topshirig'ida esa tanlangan qismlarning xizmat muddati l ga kamayadi va ular keyingi topshiriqlar uchun yangilangan holda qaytariladi.

Birinchi qatorda ikkita butun son beriladi: n va q — ombordagi ehtiyot qismlar soni va topshiriqlar soni.

Ikkinchi qatorda n ta butun son beriladi: \(a_1,a_2,...,a_n\)​ — har bir qismning xizmat muddati.

Keyingi q qatorda ikkita son beriladi: t va 𝑙.

• Agar t=0 bo'lsa — savol topshirig'i.
• Agar t=1 bo'lsa — buyruq topshirig'i.

Cheklovlar:

• \(2 ≤ n ≤ 5 × 10^5\)
• 1 ≤ q ≤ n
• \(1 ≤ l, a_i ≤ 10^5\)
• t ∈ {0, 1}

Har bir topshiriq uchun bitta qator chiqaring:

• t=0 uchun: eng kam kerakli soniyani; agar 2 ta mos qism topilmasa, −1 chiqaring.
• t=1 uchun: eng kam soniyani, so'ng tanlangan 2 ta qismning xizmat muddatlarini (pozitsiya bo'yicha o'sish tartibida); agar 2 ta mos qism topilmasa, −1 chiqaring.