The first line contains a single number $n$ ($2\le n\le 2\cdot 10^5$)~--- the size of the array $a$.

The second line contains $n$ integers $a_1,\dots,a_n$ $(1\le a_i\le 10^9)$~--- the elements of the array.

The third line contains a single integer $q$ ($1\le q\le 2\cdot 10^5$)~--- the number of queries.

Each of the next $q$ lines contains two integers $l$ and $r$ ($1\le l<r\le n$).