Most Frequent Digit in Ranges

You are given a sequence of digits and a set of queries. Each query specifies a range [L, R] (inclusive) of the sequence (with 0-based indexing). Your task is to find the digit that occurs the most frequently within that range. If more than one digit has the highest frequency, return the smallest digit among them.

Example:

Input:
10
1 2 3 0 2 2 3 4 1 0
3
0 9
1 4
2 6
Output:
2 2 2

</p>

In the first query, the entire sequence is considered. Both 2 and 1 (and possibly other digits) may appear most frequently, but the answer is the smallest digit among those with the highest count.

inputFormat

The input is read from stdin with the following format:

 n
 a1 a2 a3 ... an
 m
 L1 R1
 L2 R2
 ...
 Lm Rm

Here,

• n is the number of digits in the sequence.
• The second line contains n digits separated by spaces.
• m is the number of queries.
• Each of the following m lines contains two integers L and R indicating the range (inclusive) of the query.

outputFormat

Print a single line to stdout containing m digits separated by a single space. Each digit is the answer for the corresponding query.

## sample

10
1 2 3 0 2 2 3 4 1 0
3
0 9
1 4
2 6

2 2 2