D - Nano medidores

Languages: C, C++, Java, Pascal, Python, Tiger, JavaScript, Haskell, C#
Time & Memory limits: (details)

Fito está trabajando en el Centro Nacional de Biomedicina, en ese centro han desarrollado un sistema de nano medidores para cuantificar la actividad neurológica de los pacientes. El sistema está diseñado de la siguiente forma, se tienen N medidores numerados de 1 a N (1<= N <=100000), cada medidor i cuantifica el potencial eléctrico ki (-10000<=ki<=10000). Para realizar un rápido diagnostico se deben de realizar consultas de la forma: “cuál es la suma de los potenciales entre los medidores i y j”, Este número de consultas Q es bien elevado (0<=Q<=100000).

Input

La primera línea de la entrada es un entero N que representa la cantidad de medidores. Luego hay N líneas cada una con un entero ki. Luego un número Q que representa la cantidad de consultas que se van a realizar. Y luego Q líneas con dos enteros cada una que representan las posiciones i y j en los que se quiere saber la suma del potencial.

Output

La salida contiene Q líneas con la suma de los potenciales.

Sample test(s)

Input
5 1 2 3 -1 4 3 1 5 4 4 1 4
Output
9 -1 5