Description
UPD(2020/10/12 14:42): We update the description (new part added are in red word) for more clearly. Sorry for the inconvenience.
Spongebob and Patrick finally find out the guy with the biggest nose. But unluckily the guy is not Squidward (actually he is Barnacle Boy).
Suddenly, they see some octopus flies over.
“Well, we know one thing: it sure isn’t that guy.” said Spongebob.
Anyway Patrick is very hungry so they go to the restaurant, SAO(Seafood Around Octopuses), for their dinner. After arrving SAO, they order one Ragout Rabbit first.
They quickly eat up the Ragout Rabbit. But now they're facing a problem: they don’t know what they should order next. Patrick suggests that they could order the dish which is ordered by other customers mostly. So it’s your turn again!
There are n customers in SAO (of course not include Spongebob, Patrick and you) and they are numbered from 1 to n. Each of them orders exactly one dish. The dish ordered by the i-th customer is represented by an integer ai(the dish's number on the menu). You need to tell Spongebob and Patrick which dish is ordered mostly between the l-th, the (l+1)-th, …, the r-th customers. And if there are not only one kind of dish ordered mostly, you just need to output the dish's number which is the smallest between all the dishes ordered mostly in the range.
You have to help Spongebob and Patrick q times.
Subtask
- for testcase 1~2: ai = 1
- for testcase 3~5: ai = 1 or ai = 2
- for testcase 6~10: no additional restriction
Input
The first line contains one integer n (1 ≤ n ≤ 500) – the number of customers in SAO.
The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 500) – the number of dish each customer order.
The third line contains one integer q (1 ≤ q ≤ 500) – the times you have to help Spongebob and Patrick.
Then q lines follow. Each line contains two integer l, r (1 ≤ l ≤ r ≤ n) – the range of customers you have to find out the dish ordered mostly.
Output
For each time you help Spogebob and Patrick, output the dish's number which is ordered mostly in the range of customers(if there are not only one kind of dish ordered mostly, you just need to output the dish's number which is the smallest between all the dishes ordered mostly in the range).
Remember to print a newline('\n') at the end of the last line.