Query su intervalli più veloci

Dato un array a di n interi, dobbiamo rispondere a q interrogazioni. Tutte le interrogazioni chiedono: “Qual è la somma degli elementi dell’array a compresi tra gli indici [l; r]?” (entrambe le estremità sono incluse e l’indicizzazione inizia da 0). Questa volta la dimensione dell’array e il numero di interrogazioni sono molto più grandi. Riesci a trovare un modo per rispondere più velocemente a queste interrogazioni?

Input

La prima riga di input contiene un singolo intero n - il numero di elementi nell’array (1 ≤ n ≤ ). La riga successiva contiene n interi separati da uno spazio, che rappresentano gli elementi dell’array ().

La riga seguente contiene un singolo intero q - il numero di interrogazioni (1 ≤ q ≤ ). Le successive q righe contengono interrogazioni della forma .

Output

Il programma deve stampare q righe: ognuna dovrà contenere la somma degli elementi dell’array a compresi tra gli indici (entrambi inclusi).

Esempi