Dandelion Query

In the countryside, along the roadside, many dandelions are planted. For simplicity, we consider all dandelions as a sequence of length $n$, given by $${a_1,a_2,\dots,a_n}$$, where each $a_i$ is a positive integer representing the species identifier of the $i$-th dandelion.

For each query with an interval $[l, r]$, you need to output the species that appears most frequently in that interval. If there are multiple species with the same frequency, output the one with the smallest identifier.

Note: Your algorithm must be online.

inputFormat

The first line contains an integer $n$ --- the number of dandelions. The second line contains $n$ positive integers $a_1, a_2, \dots, a_n$. The third line contains an integer $q$ --- the number of queries. Each of the next $q$ lines contains two integers $l$ and $r$, representing a query interval.

outputFormat

For each query, output the species identifier that appears most frequently within the interval on a new line. In case of a tie, output the smallest species identifier.

sample

5
1 1 2 2 3
3
1 5
1 2
4 5

1
1
2