На круговой ленте конвейера расположены n секций, пронумерованных от 1 до n. Для каждой секции известен её вес. После секции n снова идёт секция 1, то есть лента замкнута в кольцо.

Требуется обработать q запросов. В каждом запросе заданы два номера секций l и r.

• Если l <= r, нужно найти суммарный вес секций на участке ленты от l до r.
• Если l > r, участок заворачивается через конец ленты: тогда нужно взять секции от l до n, а затем от 1 до r.

Для каждого запроса выведите суммарный вес соответствующего кругового участка.

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

В первой строке задано число n — количество секций на ленте.

Во второй строке заданы n целых чисел a_i — веса секций.

В третьей строке задано число q — количество запросов.

В следующих q строках заданы пары чисел l и r — границы участка ленты.

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

Для каждого запроса выведите одно число — суммарный вес секций на указанном участке. Каждый ответ выводите в отдельной строке.

Ограничения

• 1 <= n <= 2 * 10^5
• -10^9 <= a_i <= 10^9
• 1 <= q <= 2 * 10^5
• 1 <= l, r <= n

Ответы могут не помещаться в 32-битный целочисленный тип.

Примеры

Пример 1

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

5
-2 -1 0 1 2
8
1 1
1 5
5 1
2 4
4 2
5 5
1 2
2 1

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

-2
0
0
0
0
2
-3
0

Пример 2

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

6
1000000000 -1000000000 1000000000 -1000000000 1000000000 -1000000000
8
1 6
2 5
5 2
3 3
6 1
1 5
5 6
2 1

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

0
0
0
1000000000
0
1000000000
0
0