Problem description

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 A_i – 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 S_i, E_i, określających, że zapytanie dotyczy podciągu od S_i-tego wyrazu ciągu do E_i-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 ≤ A_i ≤ 10⁹, 1 ≤ S_i ≤ E_i ≤ N.

Przykład

5
3 1 8 2 1
3
1 3
1 5
4 4

12
15
2