#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pii pair<int,int>
#define pb push_back
const int lim=1e5+10;
int pergi[6][lim+10];
int len[6][lim+10];
int lompat[6][lim+10];
set<pii>isi[6];
int minr[6][lim+10];
int main(){
fast
int n,m;
vector<int>a(6);
int blok=316;
for(int i=1;i<=5;i++){
for(int j=1;j<=n+2;j++){
minr[i][j]=n+10;
pergi[i][j]=n+10;
lompat[i][j]=n+10;
len[i][j]=0;
}
}
vector<pii>ranges(1);
for(int i=1;i<=n;i+=blok){
ranges.pb({i,min(n,i+blok-1)});
}
for(int i=1;i<=n;i++){
int li;cin>>li;
if(li<=5)a[li]++;
}
for(int val=1;val<=5;val++){
for(int b=1;b<ranges.size();b++){
auto [b_l,b_r]=ranges[b];
int cr=n+10;
for(int i=b_r;i>=b_l;i--){
if(minr[val][i]<cr){
cr=minr[val][i];
}
lompat[val][i]=cr;
if(cr>n){
len[val][i]=0;pergi[val][i]=b_r+1;
}else if(cr>=b_r){
len[val][i]=1;pergi[val][i]=cr+1;
}else{
len[val][i]=1+len[val][cr+1];
pergi[val][i]=pergi[val][cr+1];
}
}
}
}
for(int kk=1;kk<=m;kk++){
int l,r;cin>>l>>r;
for(int val=5;val>=1;val--){
if(minr[val][l]<=r){
cout<<val<<"\n";
break;
}
auto it=isi[val].lower_bound({l,-1});
if(it!=isi[val].end()&&it->second<=r){
cout<<val<<"\n";
break;
}
int cnt_kiri=0,curr=1;
while(curr<l){
if(pergi[val][curr]-1<l){
cnt_kiri+=len[val][curr];
curr=pergi[val][curr];
}else{
if(lompat[val][curr]<l){
cnt_kiri++;
curr=lompat[val][curr]+1;
}else break;
}
}
int cnt_kanan=0;
curr=r+1;
while(curr<=n){
cnt_kanan+=len[val][curr];
curr=pergi[val][curr];
}
if(cnt_kiri+1+cnt_kanan<=a[val]){
cout<<val<<"\n";
vector<int>kotor;
kotor.pb((l-1)/blok+1);
auto it2=isi[val].upper_bound({l,n+10});
while(it2!=isi[val].begin()){
it2--;
if(it2->first<=l&&it2->second>=r){
minr[val][it2->first]=n+10;
kotor.pb((it2->first-1)/blok+1);
it2=isi[val].erase(it2);
}else if(it2->second<r){
break;
}
}
minr[val][l]=r;
isi[val].insert({l,r});
sort(kotor.begin(),kotor.end());
kotor.erase(unique(kotor.begin(),kotor.end()),kotor.end());
for(int b:kotor){
auto [b_l,b_r]=ranges[b];
int cr=n+10;
for(int i=b_r;i>=b_l;i--){
if(minr[val][i]<cr){
cr=minr[val][i];
}
lompat[val][i]=cr;
if(cr>n){
len[val][i]=0;pergi[val][i]=b_r+1;
}else if(cr>=b_r){
len[val][i]=1;pergi[val][i]=cr+1;
}else{
len[val][i]=1+len[val][cr+1];
pergi[val][i]=pergi[val][cr+1];
}
}
}
break;
}
}
}
}
