Нудне відкриття
Обмеження: 2 сек., 256 МіБ
Зеник з Марічкою — бувалі учасники олімпіад з інформатики. Вони беруть у них участь ще з тих часів, коли трава була зеленішою, довга арифметика популярнішою, а вас, дорогі дітки, не було на світі. На скільки контестів вони з’їздили ніхто точно й не скаже — вони збилися з рахунку після сорока семи.
Перед кожним солідним змаганням, у якому беруть участь Зеник і Марічка, відбувається відкриття. Сьогоднішня обласна олімпіада — не виняток.
Сьогодні наша пара разом з усіма прийшла на відкриття олімпіади. Тут організатори звертаються з вітальним словом до учасників і їхніх вчителів, розказують правила, повідомляють, які компілятори є на Алготестері, а яких нема — нічого цікавого для таких досвідчених програмістів. Тому Зеник, щоб не померти від нудьги, склав задачу та дав її розв’язати Марічці.
Задано масив a з n цілих чисел. Потрібно відповісти на q запитів: скільки є непорожніх підвідрізків з нульовою сумою на відрізку [l,r].
Не встигла й завершитися вітальна частина відкриття, як Марічка придумала розв’язок до задачі.
Вам же треба не лише придумати розв’язок, а й написати програму. Уперед!
Вхідні дані
У першому рядку задано ціле число n — розмір масиву.
У другому рядку записано n цілих чисел ai — елементи масиву.
Третій рядок містить ціле число q — кількість запитів.
У кожному з наступних q рядків записано по два цілих числа l та r — межі відрізка, для якого треба відповісти на запит.
Вихідні дані
Виведіть q цілих чисел в окремих рядках — відповіді на всі запити.
Обмеження
1≤n≤500,
|ai|≤10,
1≤q≤1000,
1≤l≤r≤n.
Оцінювання задачі складається із наступних блоків:
1 бал — приклад з умови,
14 балів — n≤100,
10 балів — без додаткових обмежень.
Бали за блок ви отримаєте лише якщо дасте правильну відповідь на всі тести з блоку.
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
5 -2 3 1 -2 1 3 1 5 2 4 3 5 | 2 0 1 |
Примітки
Відрізок [1,5] містить два підвідрізки з нульовою сумою: підвідрізок [1,4] (a1+a2+a3+a4=−2+3+1+(−2)=0) і підвідрізок [3,5] (a3+a4+a5=1+(−2)+1=0).
Відрізок [2,4] не містить жодного підвідрізка з нульовою сумою.
Відрізок [3,5] містить один підвідрізок з нульовою сумою — самого себе.