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

Limits: 2 sec., 256 MiB

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

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

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

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

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

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

Input

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

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

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

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

Output

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

Constraints

\(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 балів — без додаткових обмежень.

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

Samples

Input (stdin) сopy	Output (stdout) сopy
5 -2 3 1 -2 1 3 1 5 2 4 3 5	2 0 1

Notes

• Відрізок \([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]\) містить один підвідрізок з нульовою сумою — самого себе.