Перший рядок містить одне число $n$ ($2\le n\le 2\cdot 10^5$)~--- розмір масиву $a$.

Другий рядок містить $n$ цілих чисел $a_1,\dots,a_n$ $(1\le a_i\le 10^9)$~--- елементи масиву.

Третій рядок містить одне ціле $q$ ($1\le q\le 2\cdot 10^5$)~--- кількість запитів.

Кожен з наступних $q$ рядків містить по два цілі числа $l$ та $r$ ($1\le l<r\le n$).