#include <bits/stdc++.h>
using namespace std;
#define r(i,a,n) for(int (i)=a;i<n;i++)
#define vii vector<int,int>
#define ll long long int
#define it iterator
#define lr(i,a,n) for(long long int (i)=a;i<n;i++)
int arr[100010];
vector< pair<int,int> > stree[500010];
map<int,int> que;
int ma=0;
void merge(int parent,int c1,int c2){
int s1=stree[c1].size();
int s2=stree[c2].size();
int p1=0;
int p2=0;
while(p1<s1&&p2<s2){
if(stree[c1][p1].first==stree[c2][p2].first){
stree[parent].push_back(make_pair(stree[c1][p1].first,stree[c1][p1].second+stree[c2][p2].second));
p1++;
p2++;
}
else if(stree[c1][p1].first<stree[c2][p2].first){
stree[parent].push_back(make_pair(stree[c1][p1].first,stree[c1][p1].second));
p1++;
}
else{
stree[parent].push_back(make_pair(stree[c2][p2].first,stree[c2][p2].second));
p2++;
}
}
while(p1<s1){
stree[parent].push_back(make_pair(stree[c1][p1].first,stree[c1][p1].second));
p1++;
}
while(p2<s2){
stree[parent].push_back(make_pair(stree[c2][p2].first,stree[c2][p2].second));
p2++;
}
return;
}
void buildsegmenttree(int s,int e,int si){
if(s==e){
stree[si].push_back(make_pair(arr[s],1));
return;
}
else{
int mid=(s+e)/2;
buildsegmenttree(s,mid,si*2 + 1);
buildsegmenttree(mid+1,e,si*2 +2);
merge(si,si*2 + 1,si*2 + 2);
return;
}
}
void query(int s,int e,int qs,int qe,int si){
//cout<<s<<e<<endl;
if(s>qe || e<qs){
return;
}
if(s>=qs && e<=qe){
for(int i=0;i<stree[si].size();i++){
map<int,int>::iterator it=que.find(stree[si][i].first);
if(it==que.end()){
que.insert(make_pair(stree[si][i].first,stree[si][i].second));
ma=max(ma,stree[si][i].second);
}
else{
it->second+=(stree[si][i].second);
ma=max(ma,it->second);
}
}
return;
}
int mid;
mid=(s+e)/2;
query(s,mid,qs,qe,si*2 +1);
query(mid+1,e,qs,qe,si*2 +2);
return;
}
int main()
{
int n,q;
cin>>n>>q;
for(int i=0;i<n;i++){
cin>>arr[i];
}
buildsegmenttree(0,n-1,0);
for(int i=0;i<q;i++){
int a,b;
cin>>a>>b;
a--;
b--;
ma=0;
que.clear();
query(0,n-1,a,b,0);
cout<<ma<<endl;
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgcihpLGEsbikgZm9yKGludCAoaSk9YTtpPG47aSsrKQojZGVmaW5lIHZpaSB2ZWN0b3I8aW50LGludD4KI2RlZmluZSBsbCBsb25nIGxvbmcgaW50CiNkZWZpbmUgaXQgaXRlcmF0b3IKI2RlZmluZSBscihpLGEsbikgZm9yKGxvbmcgbG9uZyBpbnQgKGkpPWE7aTxuO2krKykKaW50IGFyclsxMDAwMTBdOwp2ZWN0b3I8IHBhaXI8aW50LGludD4gPiBzdHJlZVs1MDAwMTBdOwptYXA8aW50LGludD4gcXVlOwppbnQgbWE9MDsKdm9pZCBtZXJnZShpbnQgcGFyZW50LGludCBjMSxpbnQgYzIpewogICAgaW50IHMxPXN0cmVlW2MxXS5zaXplKCk7CiAgICBpbnQgczI9c3RyZWVbYzJdLnNpemUoKTsKICAgIGludCBwMT0wOwogICAgaW50IHAyPTA7CiAgICB3aGlsZShwMTxzMSYmcDI8czIpewogICAgICAgIGlmKHN0cmVlW2MxXVtwMV0uZmlyc3Q9PXN0cmVlW2MyXVtwMl0uZmlyc3QpewogICAgICAgICAgICBzdHJlZVtwYXJlbnRdLnB1c2hfYmFjayhtYWtlX3BhaXIoc3RyZWVbYzFdW3AxXS5maXJzdCxzdHJlZVtjMV1bcDFdLnNlY29uZCtzdHJlZVtjMl1bcDJdLnNlY29uZCkpOwogICAgICAgICAgICBwMSsrOwogICAgICAgICAgICBwMisrOwogICAgICAgIH0KICAgICAgICBlbHNlIGlmKHN0cmVlW2MxXVtwMV0uZmlyc3Q8c3RyZWVbYzJdW3AyXS5maXJzdCl7CiAgICAgICAgICAgIHN0cmVlW3BhcmVudF0ucHVzaF9iYWNrKG1ha2VfcGFpcihzdHJlZVtjMV1bcDFdLmZpcnN0LHN0cmVlW2MxXVtwMV0uc2Vjb25kKSk7CiAgICAgICAgICAgIHAxKys7CiAgICAgICAgfQogICAgICAgIGVsc2V7CiAgICAgICAgICAgIHN0cmVlW3BhcmVudF0ucHVzaF9iYWNrKG1ha2VfcGFpcihzdHJlZVtjMl1bcDJdLmZpcnN0LHN0cmVlW2MyXVtwMl0uc2Vjb25kKSk7CiAgICAgICAgICAgIHAyKys7CiAgICAgICAgfQogICAgfQogICAgd2hpbGUocDE8czEpewogICAgICAgIHN0cmVlW3BhcmVudF0ucHVzaF9iYWNrKG1ha2VfcGFpcihzdHJlZVtjMV1bcDFdLmZpcnN0LHN0cmVlW2MxXVtwMV0uc2Vjb25kKSk7CiAgICAgICAgcDErKzsKICAgIH0KICAgIHdoaWxlKHAyPHMyKXsKICAgICAgICBzdHJlZVtwYXJlbnRdLnB1c2hfYmFjayhtYWtlX3BhaXIoc3RyZWVbYzJdW3AyXS5maXJzdCxzdHJlZVtjMl1bcDJdLnNlY29uZCkpOwogICAgICAgIHAyKys7CiAgICB9CiAgICByZXR1cm47Cn0Kdm9pZCBidWlsZHNlZ21lbnR0cmVlKGludCBzLGludCBlLGludCBzaSl7CiAgICBpZihzPT1lKXsKICAgICAgICBzdHJlZVtzaV0ucHVzaF9iYWNrKG1ha2VfcGFpcihhcnJbc10sMSkpOwogICAgICAgIHJldHVybjsKICAgIH0KICAgIGVsc2V7CiAgICAgICAgaW50IG1pZD0ocytlKS8yOwogICAgICAgIGJ1aWxkc2VnbWVudHRyZWUocyxtaWQsc2kqMiArIDEpOwogICAgICAgIGJ1aWxkc2VnbWVudHRyZWUobWlkKzEsZSxzaSoyICsyKTsKICAgICAgICBtZXJnZShzaSxzaSoyICsgMSxzaSoyICsgMik7CiAgICAgICAgcmV0dXJuOwogICAgfQp9CnZvaWQgcXVlcnkoaW50IHMsaW50IGUsaW50IHFzLGludCBxZSxpbnQgc2kpewogICAvL2NvdXQ8PHM8PGU8PGVuZGw7CiAgICBpZihzPnFlIHx8IGU8cXMpewogICAgICAgIHJldHVybjsKICAgIH0KICAgIGlmKHM+PXFzICYmIGU8PXFlKXsKICAgICAgZm9yKGludCBpPTA7aTxzdHJlZVtzaV0uc2l6ZSgpO2krKyl7CiAgICAgICAgICBtYXA8aW50LGludD46Oml0ZXJhdG9yIGl0PXF1ZS5maW5kKHN0cmVlW3NpXVtpXS5maXJzdCk7CiAgICAgICAgICBpZihpdD09cXVlLmVuZCgpKXsKICAgICAgICAgICAgICBxdWUuaW5zZXJ0KG1ha2VfcGFpcihzdHJlZVtzaV1baV0uZmlyc3Qsc3RyZWVbc2ldW2ldLnNlY29uZCkpOwogICAgICAgICAgICAgIG1hPW1heChtYSxzdHJlZVtzaV1baV0uc2Vjb25kKTsKICAgICAgICAgIH0KICAgICAgICAgIGVsc2V7CiAgICAgICAgICAgICAgaXQtPnNlY29uZCs9KHN0cmVlW3NpXVtpXS5zZWNvbmQpOwogICAgICAgICAgICAgIG1hPW1heChtYSxpdC0+c2Vjb25kKTsKICAgICAgICAgIH0KICAgICAgIH0KICAgICAgICByZXR1cm47CiAgICB9CiAgICBpbnQgbWlkOwogICAgbWlkPShzK2UpLzI7CiAgICBxdWVyeShzLG1pZCxxcyxxZSxzaSoyICsxKTsKICAgIHF1ZXJ5KG1pZCsxLGUscXMscWUsc2kqMiArMik7CiAgICByZXR1cm47Cn0KaW50IG1haW4oKQp7CiAgICBpbnQgbixxOwogICAgY2luPj5uPj5xOwogICAgZm9yKGludCBpPTA7aTxuO2krKyl7CiAgICAgICAgY2luPj5hcnJbaV07CiAgICB9CiAgICBidWlsZHNlZ21lbnR0cmVlKDAsbi0xLDApOwogICAgZm9yKGludCBpPTA7aTxxO2krKyl7CiAgICAgICAgaW50IGEsYjsKICAgICAgICBjaW4+PmE+PmI7CiAgICAgICAgYS0tOwogICAgICAgIGItLTsKICAgICAgICBtYT0wOwogICAgICAgcXVlLmNsZWFyKCk7CiAgICAgICBxdWVyeSgwLG4tMSxhLGIsMCk7CiAgICAgICBjb3V0PDxtYTw8ZW5kbDsKICAgIH0KICAgIHJldHVybiAwOwp9Cg==