11235

#include <iostream>
#include <vector>
#include <map>
#include <cmath>
#include <fstream>
using namespace std;

#define rep(i,n) for(__typeof(n) i=0; i<(n); i++)
#define READ(f) freopen(f, "r", stdin)

#define Max 100010
vector <int> segment_tree;

int data[Max];
size_t arrLength;


void initSegmentTree() {
    int length = 2 * pow(2.0, floor(log((double) arrLength ) / log(2.0)) + 1 );
    segment_tree.clear();
    segment_tree.resize(length, 0);
}


void buildHelper( int node, int begin, int end ) {
    if (begin == end) {
        segment_tree[node] = begin;
        return;
    }
    int leftIndx = 2 * node, rightIndx = 2 * node + 1;

    buildHelper( leftIndx, begin, (begin + end) / 2);
    buildHelper(rightIndx, (begin + end) / 2 + 1, end);

    int lContent = segment_tree[leftIndx], rContent = segment_tree[rightIndx];

    segment_tree[node] = ( data[lContent] >= data[rContent] ) ? lContent : rContent;

}

void buildSegmentTree() {
    buildHelper(1, 0, arrLength - 1);
}

int queryHelper( int node, int begin, int end, int i, int j) {
    if (i > end || j < begin) return -1;

    if (begin >= i && end <= j) return segment_tree[node];

    int pos1 = queryHelper(2 * node, begin, (begin + end) / 2, i, j);
    int pos2 = queryHelper(2 * node + 1, (begin + end) / 2 + 1, end, i, j);

    if(pos1 == -1) return pos2;
    if(pos2 == -1) return pos1;

    return (data[pos1] >= data[pos2]) ? pos1 : pos2;
}

int query(int lower, int upper) {
    return queryHelper(1, 0, arrLength - 1, lower, upper);
}

int main() {
    READ("in.txt");
    int n, q, begin, end;
    while(cin >> n && n) {
        cin >> q;
        arrLength = n;
        map <int , int> track;
        rep(i, n) {
            cin >> data[i];
            track[data[i]] += 1;
        }
        rep(i, n) data[i] = track[data[i]];
        initSegmentTree();
        buildSegmentTree();
        rep(i, q) {
            cin >> begin >> end;
            if(begin > 1 || end < arrLength) {
                if(begin != 1 && end != arrLength) {
                    int subq1 = 1, subq2 = 1, result = 0;
                    if(data[begin - 1 - 1] == data[begin - 1]) {
                        for(int i = begin - 1 + 1; data[begin - 1] == data[i]; i++) subq1++;
                    }
                    if(data[end - 1 + 1] == data[end - 1]) {
                        for(int i = end - 1 - 1; data[end - 1] == data[i]; i--) subq2++;
                    }
                    // may be here is a problem
                    if((end - begin + 1) - (subq1 + subq2) > 0) {
                        int temp = max(subq1, data[query(begin - 1 + subq1, end - 1 - subq2)]);
                        result = max(temp, subq2);
                    } else result = (subq1, subq2);
                    cout << result << "\n";
                } else if(begin != 1 && end == arrLength) {
                    if(data[begin - 1 - 1] == data[begin - 1]) {
                        int subq = 1;
                        for(int i = begin - 1 + 1; data[begin - 1] == data[i]; i++) subq++;
                        cout << max(data[query(begin - 1 + subq, end - 1)], subq) << "\n";
                    } else cout << data[query(begin - 1, end - 1)] << "\n";
                } else {
                    if(data[end - 1 + 1] == data[end - 1]) {
                        int subq = 1;
                        for(int i = end - 1 - 1; data[end - 1] == data[i]; i--) subq++;
                        cout << max(data[query(begin - 1, end - 1 - subq)], subq) << "\n";
                    } else cout << data[query(begin - 1, end - 1)] << "\n";
                }
            } else cout << data[query(begin - 1, end - 1)] << "\n";
        }
    }
    return 0;
}