Masala C

Matematik detektivga tayyormisiz? Sizda uzunligi \(n\) ga teng va \(\text{natural}\) sonlardan tashkil topgan sirli massiv bor. Sizga \(q\) ta sirli so'rovlar beriladi. Har bir so'rov quyidagicha:

• \(l\) va \(r\) indekslari beriladi. Siz ushbu oraliqni \([l,\ r]\) ikkiga bo'lib beruvchi \(k\) (\(l\leq k < r\)) shunday nuqtani topingki, \(\left|\sum_{i=l}^{k} a_i - \sum_{i=k+1}^{r} a_i\right|\) (ya'ni, bo'lingan ikkala qismining yig'indisi farqi) minimal bo'lsin. Agar bunday \(k\) bir nechta bo'lsa, eng kichik \(k\)ni tanlang!

Har bir javob oddiy emas — eng aniq va muvozanatli bo'linishni topishga harakat qiling!

Birinchi qatorda \(1 \le n,\ q \le 10^5\) sonlari kiritiladi

Ikkinchi qatorda massiv kiritiladi \(1 \le a_i \le 10^9\)

Keyingi q ta qatorda \(1 \le l < r \le n\) sonlari kiritiladi.

Subtasklar:

• \(Subtask\ 1.\ \text{Massivdagi har bir element bir xil, ya'ni}\ a_i = \ \text{const}\ (11\ \text{ball})\)
• \(Subtask\ 2.\ n,\ q\ (n,\ q \le 100)\ (12\ \text{ball})\)
• \(Subtask\ 3.\ n,\ q\ (n,\ q \le 5000)\ (23\ \text{ball})\)
• \(Subtask\ 4.\ \text{To'liq yechim}\ (54\ \text{ball})\)

Har bir so'rov uchun masala yechimini chiqaring

Eslatma!! python dasturlash tilidan foydalanuvchilar pypy compilatoridan foydalanishni maslahat beramiz