E. Функция
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Серега и Федя играют с функциями. Однажды им попалась очень интересная функция. Выглядит она так:

  • f(1, j) = a[j], 1 ≤ j ≤ n.
  • f(i, j) = min(f(i - 1, j), f(i - 1, j - 1)) + a[j], 2 ≤ i ≤ n, i ≤ j ≤ n.

Здесь a — целочисленный массив длины n.

Серега и Федя хотят знать значение этой функции в некоторых точках. Но вычислять вручную значения им не хочется. Поэтому они просят помощи у вас.

Входные данные

В первой строке содержится целое число n (1 ≤ n ≤ 105) — длина массива a. Следующая строка содержит n целых чисел: a[1], a[2], ..., a[n] (0 ≤ a[i] ≤ 104).

В следующей строке записано целое число m (1 ≤ m ≤ 105) — количество запросов. Каждая из следующих m строк содержит по два целых числа: xi, yi (1 ≤ xi ≤ yi ≤ n). Числа обозначают, что Федя и Серега хотят узнать, чему равно f(xi, yi).

Выходные данные

Выведите m строк — ответы на запросы ребят.

Примеры
Входные данные
6
2 2 3 4 3 4
4
4 5
3 4
3 4
2 3
Выходные данные
12
9
9
5
Входные данные
7
1 3 2 3 4 0 2
4
4 5
2 3
1 4
4 6
Выходные данные
11
4
3
0