Descripción

Durante \(N\) días tu amiguito decide darte cierta cantidad de mangos en muestra de su afecto. Tu tarea es responder cuántos mangos recibiste entre ciertos rangos de días.

Entrada

• En la primera línea \(N\) días.
• En la segunda línea, \(N\) cantidades de mangos por días.
• En la tercer línea, \(Q\) peguntas que debes responder.
• En las siguientes \(Q\) líneas, el día de inicio \((L)\) y fin \((R)\).

Salida

Por cada pregunta, la cantidad de mangos que recibiste.

Ejemplo

Entrada

10
1 2 3 4 5 6 7 8 9 10
3
1 8 
4 7
2 10

Salida

36
22
54

Límites

• \(1 \leq L \leq R \leq N \leq 10^6\)
• \(1 \leq Q \leq 10^6\)