题目描述

对于一个长度为$\red n$的正整数序列，$\red{a_1,a_2......a_n}$,输入$\red m$表示$\red m$组测试数据，

对于每组数据输入$\red i$,$\red j$，输出$\red{a_i}$到$\red{a_j}$中出现次数最多的数，如果出现次数相同，则取比较小的那个数。

输入格式

第一行包含一个正整数$\red n$;

第二行包含$\red n$个正整数，用空格隔开；

第三行包含一个正整数$\red m$；

接下来的$\red m$行数据每行包含两个数据$\red i$,$\red j$，以空格隔开；

输出格式

共$\red m$行， 每行一个正整数表示从ai到aj中出现次数最多的数；

样例

输入样例

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

输出样例

3
4

提示

对于所有的数据满足: $\red{1 \le n \le 100,m < n ; 1<i < j < 100}$;