/*

查询区间众数，要求强制在线

设有T个块

1.众数只可能在大块[L,R]里或者两端[l,L) (R,r]里出现

2.大块的众数只要预处理打表一下即可，复杂度n*T(这样的区间有T*T个)

3.两端的众数需要枚举每个元素，然后查询这个元素在区间[l,r]里出现的次数

    用一个vector记录每个值出现的位置，然后用二分找其在区间[l,r]出现的次数即可

        这部分每次查询的复杂度是N/T*logN，

    块长取sqrt(nlogn)

*/

#include<bits/stdc++.h>

using namespace std;

#define maxn 100005

int id,n,len,pos[maxn],v[maxn],val[maxn],f[][];

vector<int>ve[maxn];

map<int,int>mp;//哈希表

int cnt[maxn];

void pre(int p){//处理第p块到n整块区间众数

    memset(cnt,,sizeof cnt);

    int mx=,ans=;

    for(int i=(p-)*len+;i<=n;i++){

        cnt[v[i]]++;

        int t=pos[i];

        if(cnt[v[i]]>mx || cnt[v[i]]==mx && val[v[i]]<val[ans])

            ans=v[i],mx=cnt[v[i]];

        f[p][t]=ans;

    }

}

int query(int l,int r,int x){//查询[l,r]区间x出现了几次

    int t=upper_bound(ve[x].begin(),ve[x].end(),r)-lower_bound(ve[x].begin(),ve[x].end(),l);

    return t;

}

int query(int a,int b){

    int ans,mx,p=pos[a],q=pos[b];

    ans=f[p+][q-];

    mx=query(a,b,ans);

    for(int i=a;i<=min(p*len,b);i++){

        int t=query(a,i,v[i]);

        if(t>mx || t==mx&&val[v[i]]<val[ans])

            ans=v[i],mx=t;

    }

    if(p!=q)

        for(int i=(q-)*len+;i<=b;i++){

            int t=query(i,b,v[i]);

            if(t>mx || t==mx&&val[v[i]]<val[ans])

                ans=v[i],mx=t;

        }

    return ans;

}

int main(){

    cin>>n;len=;

    for(int i=;i<=n;i++){

        cin>>v[i];

        if(mp[v[i]]==){

            mp[v[i]]=++id;

            val[id]=v[i];

        }

        v[i]=mp[v[i]];

        ve[v[i]].push_back(i);

    }

    for(int i=;i<=n;i++)

        pos[i]=(i-)/len+;

    for(int i=;i<=pos[n];i++)

        pre(i);//预处理

    for(int i=;i<=n;i++){

        int a,b;

        cin>>a>>b;

        if(a>b)swap(a,b);

        cout<<val[query(a,b)]<<endl;

    }

}