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

Улаз

Са стандардног улаза се уноси број дана \(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