Нудне відкриття

Обмеження: 2 сек., 256 МіБ

Зеник з Марічкою — бувалі учасники олімпіад з інформатики. Вони беруть у них участь ще з тих часів, коли трава була зеленішою, довга арифметика популярнішою, а вас, дорогі дітки, не було на світі. На скільки контестів вони з’їздили ніхто точно й не скаже — вони збилися з рахунку після сорока семи.

Перед кожним солідним змаганням, у якому беруть участь Зеник і Марічка, відбувається відкриття. Сьогоднішня обласна олімпіада — не виняток.

Сьогодні наша пара разом з усіма прийшла на відкриття олімпіади. Тут організатори звертаються з вітальним словом до учасників і їхніх вчителів, розказують правила, повідомляють, які компілятори є на Алготестері, а яких нема — нічого цікавого для таких досвідчених програмістів. Тому Зеник, щоб не померти від нудьги, склав задачу та дав її розв’язати Марічці.

Задано масив $a$ з $n$ цілих чисел. Потрібно відповісти на $q$ запитів: скільки є непорожніх підвідрізків з нульовою сумою на відрізку $[l, r]$.

Не встигла й завершитися вітальна частина відкриття, як Марічка придумала розв’язок до задачі.

Вам же треба не лише придумати розв’язок, а й написати програму. Уперед!

Вхідні дані

У першому рядку задано ціле число $n$ — розмір масиву.

У другому рядку записано $n$ цілих чисел $a_i$ — елементи масиву.

Третій рядок містить ціле число $q$ — кількість запитів.

У кожному з наступних $q$ рядків записано по два цілих числа $l$ та $r$ — межі відрізка, для якого треба відповісти на запит.

Вихідні дані

Виведіть $q$ цілих чисел в окремих рядках — відповіді на всі запити.

Обмеження

$1 \le n \le 500$,

$|a_i| \le 10$,

$1 \le q \le 1000$,

$1 \le l \le r \le n$.

Оцінювання задачі складається із наступних блоків:

1 бал — приклад з умови,

14 балів — $n \le 100$,

10 балів — без додаткових обмежень.

Бали за блок ви отримаєте лише якщо дасте правильну відповідь на всі тести з блоку.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
5 -2 3 1 -2 1 3 1 5 2 4 3 5	2 0 1

Примітки

• Відрізок $[1, 5]$ містить два підвідрізки з нульовою сумою: підвідрізок $[1, 4]$ ($a_1+a_2+a_3+a_4=-2+3+1+(-2)=0$) і підвідрізок $[3, 5]$ ($a_3+a_4+a_5=1+(-2)+1=0$).

• Відрізок $[2, 4]$ не містить жодного підвідрізка з нульовою сумою.

• Відрізок $[3, 5]$ містить один підвідрізок з нульовою сумою — самого себе.