/*
    离散化并创建一个数组b，储存上一个比自己频数大的下标lastinx
    查询时二分或者哈希查端点处数字长度，中间的利用数组b的lastinx从右端点向左跳跃查找
    一次查询最糟糕情况复杂度应该是sqrt(n)
*/
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 100003;

struct Item {
    int len, inx, lastinx;
} stk[N], b[N];
int a[N], bscmap[N], inx, stkinx;

int inline stkpush(int i, int len) {
    for (; stkinx && stk[stkinx - 1].len <= len; stkinx--);
    stk[stkinx].len = len;
    stk[stkinx].inx = i;
    return stkinx > 0 ? stk[stkinx - 1].inx : -1;
}

int inline query(int l, int r) {
    int k, lenl, lenr;
    lenl = bscmap[l], lenr = bscmap[r];
    k = lenr - 1;
    for (; k >= 0 && b[k].lastinx >= 0 && b[b[k].lastinx].inx >= l;)
        k = b[k].lastinx;
    lenl = min(b[lenl].inx + b[lenl].len - 1, r) - l + 1;
    lenr = r - max(b[lenr].inx, l) + 1;
    k = (k >= 0 && b[k].inx >= l) ? b[k].len : -1;
    return max(k, max(lenl, lenr));
}

int main(void) {
    int n, m;
    for (; ~scanf("%d", &n), n;) {
        scanf("%d%d", &m, a);
        bscmap[0] = inx = stkinx = 0;
        b[0].len = 1;
        b[0].inx = 0;
        b[0].lastinx = -1;
        for (int i = 1; i < n; i++) {
            scanf("%d", a + i);
            if (a[i] == a[i - 1])
                b[inx].len++;
            else {
                b[inx].lastinx = stkpush(inx, b[inx].len);
                stkinx++;
                b[++inx].len = 1;
                b[inx].inx = i;
            }
            bscmap[i] = inx;
        }
        b[inx].lastinx = stkpush(inx, b[inx].len);
        for (int l, r; m--;) {
            scanf("%d%d", &l, &r);
            printf("%d\n", query(l - 1, r - 1));
        }
    }
    return 0;
}