Elections

Recently the country held an election that used modern technology. For each ballot, it is known when it was put into the box and which candidate the voter chose. After the votes were counted, everyone wanted to analyze how the election went. Why else would the whole system have been introduced?

Many people wanted to know the following: for a given time interval, which candidate received the most votes? If a candidate got many votes in a short interval and fewer outside it, fraud may have happened during that interval. A site was built to answer such questions, but the number of visitors was unexpectedly large, and the site could not keep up with the load.

The management decided to rewrite the site so that it serves $m$ users at the same time. Your task is to write a program that answers the question users ask: which candidate received the most votes in a given interval?

The first line contains the number of processed ballots $n$ ($1 \leq n \leq 100,000$).

The second line contains $n$ integers $a_i$ separated by spaces ($1 \leq a_i \leq 10^9$). Here $a_i$ is the number of the candidate chosen by the voter who put ballot number $i$ into the box.

The third line contains the number of queries $m$ ($1 \leq m \leq 100,000$).

Each of the next $m$ lines contains a query $l_i$ $r_i$ ($1 \leq l_i \leq r_i \leq n$).

For each query, print one number on a separate line: the number of the most popular candidate among the ballots numbered from $l_i$ to $r_i$, inclusive.

A candidate is the most popular if no other candidate received more votes among those ballots. Ties are allowed.

For the last query of the sample, the answer 1 is also accepted. Ololo, partial solutions.