Задано набір чисел 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.