Obeleži sve kategorije koje odgovaraju problemu

Позната је зарада једног предузећа током одређеног броја дана. Напиши програм који омогућава кориснику да израчунава укупну зараду предузећа у временским периодима одређеним почетним и крајњим даном.

Улаз

Са стандардног улаза се уноси број дана $n$ ($1 \leq n \leq 100000$), а затим у наредном реду $n$ целих бројева између $0$ и $100$, раздвојених са по једним размаком, који представљају зараде током $n$ дана. Након тога се уноси број упита $m$ ($1 \leq m \leq 100000$) и у наредних $m$ редова се уносе временски периоди одређени редним бројем почетног дана $a$ и крајњег дана $b$ ($0 \leq a \leq b < n$).

Излаз

На стандардни излаз исписати $m$ целих бројева који представљају укупне зараде у сваком од $m$ периода.

Пример

Улаз

5
1 2 3 4 5
3
0 4
1 3
2 2

Излаз

15
9
3