Masala #1151

Xotira 20 MB Vaqt 1000 ms
14

Noodatiy so'rov

Davron massivlar bilan o'yin o'ynashni juda yaxshi bo'radi. Davronda N uzunlikka ega \(c_1, c_2, ..., c_N\)massivi bor. Bir kuni u quyidagi o'yinni o'ynamoqchi bo'ldi, massivning [L, R] oralig'ini kesib oladi va summasi 0 ga teng bo'ladigan va bir biri bilan kesishmaydigan qism massivlar sonini aniqlaydi. Lekin bu ishni bajarish juda ko'p vaqt olgani uchun Davron sizlardan yordam so'ramoqda. Davronning ishini tezlashtiruvchi dastur tuzing.


Kiruvchi ma'lumotlar:

Kirish faylining birinchi qatorida N natural soni mavjud \((1 \le N \le 4*10^5)\).

Keyingi qatorda N ta butun son - massiv elementlari joylashgan \((-10^9 \le c_i \le 10^9)\).

Uchinchi qatorda so'rovlar soni - Q kiritiladi \((1 \le Q \le 4*10^5)\).

Keyingi Q ta qatorning har birida ikkita butun son L va R mavjud \((1 \le L \le R \le N)\).


Chiquvchi ma'lumotlar:

Chiqish fayliga har bir so'rov uchun alohida qatorda massivning [L, R] oralig'ida yig'indisi 0 ga teng bo'lgan qism massivlar sonini chop eting.


Misollar
# input.txt output.txt
1
10
1 2 -3 0 1 -4 3 2 -1 1
3
1 10
1 5
2 9
4
2
2
Izoh:

Qism massiv - massivning o'ng va chap tomonidan 0 yoki bir nechta elementlarini qirqib tashlashdan hosil bo'lgan massiv.

Masalan bizga berilgan massiv [1, 2, 3, 4, 5] bo'lsin. Bunday holatda ushbu massivning qism massivlari deb quyidagilarni aytishimiz mumkin: [1, 2], [3, 4, 5], [2, 3, 4] ... . [1, 2, 4], [3, 5] lar esa qism massiv bo'la olmaydi.

Birinchi misolga izoh:

1-so'rovda: [{1, 2, -3}, {0}, {1, -4, 3}, 2, {-1, 1}]

2-so'rovda: [{1, 2, -3}, {0}, 1]

3-so'rovda: [2, -3, {0}, {1, -4, 3}, 2, -1, 1]