Problem description


Trudniejsze sumowanie
(sumowanie-2)
Memory limit: 32 MB
Time limit: 4.00 s

Pamiętasz zadanie Sumowanie? Było banalne prawda? No to pora je trochę utrudnić.

Mamy ciąg N liczb całkowitych oraz Q zapytań postaci: Jaka jest suma elementów od pewnego do pewnego elementu ciągu? (np. od piątego do dziewiątego).

Napisz program, który: wczyta ciąg liczb oraz zapytania dotyczące sumy pewnych spójnych podciągów tego ciągu, wyznaczy dla każdego z zapytań sumę liczb leżących w tym spójnym podciągu i wypisze wyniki na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, określająca długość ciągu. W drugim wierszu wejścia znajduje się ciąg N nieujemnych liczb całkowitych Ai – liczby ciągu, który rozważamy. W trzecim wierszu wejścia znajduje się jedna liczba naturalna Q, określająca liczbę zapytań. W kolejnych Q wierszach znajdują się opisy zapytań, po jednym w wierszu. Opis każdego zapytania składa się z dwóch liczb całkowitych Si, Ei, określających, że zapytanie dotyczy podciągu od Si-tego wyrazu ciągu do Ei-tego wyrazu ciągu.

Wyrazy ciągu numerujemy kolejnymi liczbami naturalnymi od 1 do N.

Wyjście

Twój program powinien wypisać na wyjście Q wierszy. W i-tym wierszu powinna się znaleźć odpowiedź dla i-tego zapytania. Odpowiedź dla każdego zapytania to jedna liczba całkowita – suma liczb ciągu leżących w przedziale z zapytania.

Ograniczenia

1 ≤ N ≤ 500 000, 1 ≤ Q ≤ 500 000, 0 ≤ Ai ≤ 109, 1 ≤ Si ≤ Ei ≤ N.

Przykład

Input Output
5
3 1 8 2 1
3
1 3
1 5
4 4
12
15
2