#include <bits/stdc++.h>
using namespace std;
const int SIZE = (int)1e5+10;
int f[2*SIZE], a[2*SIZE]; // f = frequency array, a = input array
vector <unordered_set <int> > S( 2*SIZE );
int ans, sq;
bool cmp( tuple <int, int, int>& a, tuple <int, int, int>& b ) {
if( get<0>(a)/sq != get<0>(b)/sq )
return get<0>(a) < get<0>(b);
return get<1>(a) < get<1>(b);
}
void extend( int index ) {
int v = a[index];
if( f[v] > 0 )
S[f[v]].erase( v );
f[v]++;
if( f[v] > 0 )
S[f[v]].insert( v );
if( f[v] > ans )
ans += 1;
}
void shrink( int index ) {
int v = a[index];
if( f[v] > 0 )
S[f[v]].erase( v );
f[v]--;
if( f[v] > 0 )
S[f[v]].insert( v );
if( ans > 0 && S[ans].size() == 0 )
ans -= 1;
}
int main( int argc, char *argv[] ) {
int n, q, L, R;
while( scanf("%d", &n) && n != 0 ) {
// clear the data structures
memset(f, 0, sizeof f);
for( int i = 0; i < 2*SIZE; i++ )
S[i].clear();
scanf("%d", &q);
sq = sqrt(n);
for( int i = 0; i < n; i++ ) {
scanf("%d", &a[i]);
if( a[i] < 0 ) // -x will be transformed to SIZE + x
a[i] = abs(a[i]) + SIZE;
}
vector <tuple <int, int, int> > query(q);
int answer[q];
for( int i = 0; i < q; i++ ) {
scanf("%d %d", &L, &R);
query[i] = make_tuple( L-1, R-1, i ); // 0-based indexing
}
sort( query.begin(), query.end(), cmp );
int currentL = get<0>( query[0] );
int currentR = currentL;
f[a[currentL]]++;
S[f[a[currentL]]].insert( a[currentL] );
ans = 1;
for( int i = 0; i < q; i++ ) {
L = get<0>( query[i] ), R = get<1>( query[i] );
while( currentL < L ) {
shrink( currentL );
++currentL;
}
while( currentL > L ) {
--currentL;
extend( currentL );
}
while( currentR < R ) {
++currentR;
extend( currentR );
}
while( currentR > R ) {
shrink( currentR );
--currentR;
}
answer[ get<2>(query[i]) ] = ans;
}
for( int i = 0; i < q; i++ )
printf("%d\n", answer[i]);
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpjb25zdCBpbnQgU0laRSA9IChpbnQpMWU1KzEwOwppbnQgZlsyKlNJWkVdLCBhWzIqU0laRV07CQkJLy8gZiA9IGZyZXF1ZW5jeSBhcnJheSwgYSA9IGlucHV0IGFycmF5CnZlY3RvciA8dW5vcmRlcmVkX3NldCA8aW50PiA+IFMoIDIqU0laRSApOwppbnQgYW5zLCBzcTsKCmJvb2wgY21wKCB0dXBsZSA8aW50LCBpbnQsIGludD4mIGEsIHR1cGxlIDxpbnQsIGludCwgaW50PiYgYiApIHsKCiAgICBpZiggZ2V0PDA+KGEpL3NxICE9IGdldDwwPihiKS9zcSApCiAgICAgICAgcmV0dXJuIGdldDwwPihhKSA8IGdldDwwPihiKTsKICAgIHJldHVybiBnZXQ8MT4oYSkgPCBnZXQ8MT4oYik7Cn0KCnZvaWQgZXh0ZW5kKCBpbnQgaW5kZXggKSB7CgkKCWludCB2ID0gYVtpbmRleF07CiAgICBpZiggZlt2XSA+IDAgKQogICAgICAgIFNbZlt2XV0uZXJhc2UoIHYgKTsKICAgIGZbdl0rKzsKICAgIGlmKCBmW3ZdID4gMCApCiAgICAgICAgU1tmW3ZdXS5pbnNlcnQoIHYgKTsKCiAgICBpZiggZlt2XSA+IGFucyApCiAgICAgICAgYW5zICs9IDE7Cn0KCnZvaWQgc2hyaW5rKCBpbnQgaW5kZXggKSB7CgkKCWludCB2ID0gYVtpbmRleF07CiAgICBpZiggZlt2XSA+IDAgKQogICAgICAgIFNbZlt2XV0uZXJhc2UoIHYgKTsKICAgIGZbdl0tLTsKICAgIGlmKCBmW3ZdID4gMCApCiAgICAgICAgU1tmW3ZdXS5pbnNlcnQoIHYgKTsKCiAgICBpZiggYW5zID4gMCAmJiBTW2Fuc10uc2l6ZSgpID09IDAgKQogICAgICAgIGFucyAtPSAxOwp9CgppbnQgbWFpbiggaW50IGFyZ2MsIGNoYXIgKmFyZ3ZbXSApIHsKCiAgICBpbnQgbiwgcSwgTCwgUjsKICAgIHdoaWxlKCBzY2FuZigiJWQiLCAmbikgJiYgbiAhPSAwICkgewoKCQkvLyBjbGVhciB0aGUgZGF0YSBzdHJ1Y3R1cmVzCiAgICAgICAgbWVtc2V0KGYsIDAsIHNpemVvZiBmKTsKICAgICAgICBmb3IoIGludCBpID0gMDsgaSA8IDIqU0laRTsgaSsrICkKICAgICAgICAgICAgU1tpXS5jbGVhcigpOwogICAgICAgIAogICAgICAgIHNjYW5mKCIlZCIsICZxKTsKICAgICAgICBzcSA9IHNxcnQobik7CiAgICAgICAgZm9yKCBpbnQgaSA9IDA7IGkgPCBuOyBpKysgKSB7CiAgICAgICAgICAgIHNjYW5mKCIlZCIsICZhW2ldKTsKICAgICAgICAgICAgaWYoIGFbaV0gPCAwICkJCQkJLy8gLXggd2lsbCBiZSB0cmFuc2Zvcm1lZCB0byBTSVpFICsgeAogICAgICAgICAgICAgICAgYVtpXSA9IGFicyhhW2ldKSArIFNJWkU7CiAgICAgICAgfQogICAgICAgIAogICAgICAgIHZlY3RvciA8dHVwbGUgPGludCwgaW50LCBpbnQ+ID4gcXVlcnkocSk7CiAgICAgICAgaW50IGFuc3dlcltxXTsKCiAgICAgICAgZm9yKCBpbnQgaSA9IDA7IGkgPCBxOyBpKysgKSB7CiAgICAgICAgICAgIHNjYW5mKCIlZCAlZCIsICZMLCAmUik7CiAgICAgICAgICAgIHF1ZXJ5W2ldID0gbWFrZV90dXBsZSggTC0xLCBSLTEsIGkgKTsJLy8gMC1iYXNlZCBpbmRleGluZwogICAgICAgIH0KICAgICAgICAKICAgICAgICBzb3J0KCBxdWVyeS5iZWdpbigpLCBxdWVyeS5lbmQoKSwgY21wICk7CgogICAgICAgIGludCBjdXJyZW50TCA9IGdldDwwPiggcXVlcnlbMF0gKTsKICAgICAgICBpbnQgY3VycmVudFIgPSBjdXJyZW50TDsKICAgICAgICBmW2FbY3VycmVudExdXSsrOwogICAgICAgIFNbZlthW2N1cnJlbnRMXV1dLmluc2VydCggYVtjdXJyZW50TF0gKTsKICAgICAgICBhbnMgPSAxOwoKICAgICAgICBmb3IoIGludCBpID0gMDsgaSA8IHE7IGkrKyApIHsKICAgICAgICAgICAgCiAgICAgICAgICAgIEwgPSBnZXQ8MD4oIHF1ZXJ5W2ldICksIFIgPSBnZXQ8MT4oIHF1ZXJ5W2ldICk7CiAgICAgICAgICAgIHdoaWxlKCBjdXJyZW50TCA8IEwgKSB7CgogICAgICAgICAgICAgICAgc2hyaW5rKCBjdXJyZW50TCApOwogICAgICAgICAgICAgICAgKytjdXJyZW50TDsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgd2hpbGUoIGN1cnJlbnRMID4gTCApIHsKCiAgICAgICAgICAgICAgICAtLWN1cnJlbnRMOwogICAgICAgICAgICAgICAgZXh0ZW5kKCBjdXJyZW50TCApOwogICAgICAgICAgICB9CgogICAgICAgICAgICB3aGlsZSggY3VycmVudFIgPCBSICkgewoKICAgICAgICAgICAgICAgICsrY3VycmVudFI7CiAgICAgICAgICAgICAgICBleHRlbmQoIGN1cnJlbnRSICk7CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIHdoaWxlKCBjdXJyZW50UiA+IFIgKSB7CgogICAgICAgICAgICAgICAgc2hyaW5rKCBjdXJyZW50UiApOwogICAgICAgICAgICAgICAgLS1jdXJyZW50UjsKICAgICAgICAgICAgfQogICAgICAgICAgICBhbnN3ZXJbIGdldDwyPihxdWVyeVtpXSkgXSA9IGFuczsKICAgICAgICB9CiAgICAgICAgZm9yKCBpbnQgaSA9IDA7IGkgPCBxOyBpKysgKQogICAgICAgICAgICBwcmludGYoIiVkXG4iLCBhbnN3ZXJbaV0pOwogICAgfQogICAgcmV0dXJuIDA7Cn0=