Задан набор чисел a1, ..., an. Для заданных индексов l и r найдите

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

В первой строке записано количество чисел n (1 ≤ n ≤ 106). Во второй строке записаны числа ai (1 ≤ ai ≤ 1000), разделенные пробелом. На третьей строке записано число m (1 ≤ m ≤ 106) - количество запросов. Далее на отдельных строках записаны сами запросы li и ri (1 ≤ li ≤ ri ≤ n).

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

Выведите в отдельных строках m чисел Sli..ri.