Серега и Федя играют с функциями. Однажды им попалась очень интересная функция. Выглядит она так:
Здесь 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
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач