/* Walter Guttmann */
#include <cassert>
#include <fstream>
#include <iostream>

using namespace std;

#define inp cin

const int maxn = 1<<20;
const int max2 = 2*maxn;

int data[maxn];
int pre[max2], in[max2], suf[max2];
int dpre[max2], din[max2], dsuf[max2];

int main() {
  int n;
  while (inp >> n) {
    if (n == 0) break;
    assert(n <= maxn);
    int q;
    inp >> q;
    int ofs = 1;
    while (ofs < n)
      ofs *= 2;
    for (int i=0 ; i<n ; i++) {
      inp >> data[i];
      pre[ofs+i] = in[ofs+i] = suf[ofs+i] = 1;
      dpre[ofs+i] = din[ofs+i] = dsuf[ofs+i] = data[i];
    }
    for (int i=n ; i<ofs ; i++)
      pre[ofs+i] = in[ofs+i] = suf[ofs+i] = 0;
    for (int i=ofs-1 ; i>0 ; i--) {
      dpre[i] = dpre[2*i];
      pre[i] = pre[2*i] + (dpre[2*i] == dpre[2*i+1] ? pre[2*i+1] : 0);
      dsuf[i] = dsuf[2*i+1];
      suf[i] = suf[2*i+1] + (dsuf[2*i] == dsuf[2*i+1] ? suf[2*i] : 0);
      din[i] = din[2*i];
      in[i] = in[2*i];
      if (dsuf[2*i] == dpre[2*i+1] && in[i] < suf[2*i] + pre[2*i+1]) {
        in[i] = suf[2*i] + pre[2*i+1];
        din[i] = dsuf[2*i];
      }
      if (in[i] < in[2*i+1]) {
        in[i] = in[2*i+1];
        din[i] = din[2*i+1];
      }
    }
    while (q--) {
      int from, to;
      inp >> from >> to;
      assert(1 <= from && from <= to && to <= n);
      --from;
      --to;
      int fsuf, fin, fdin, tpre, tin, tdin;
      fsuf = fin = tpre = tin = 1;
      fdin = data[from];
      tdin = data[to];
      for (from += ofs, to += ofs ; from/2 != to/2 ; from /= 2, to /= 2) {
        if (from % 2 == 0) {
          if (dsuf[from] == dpre[from+1] && fin < fsuf + pre[from+1]) {
            fin = fsuf + pre[from+1];
            fdin = dsuf[from];
          }
          if (fin < in[from+1]) {
            fin = in[from+1];
            fdin = din[from+1];
          }
          fsuf = suf[from+1] + (dsuf[from] == dsuf[from+1] ? fsuf : 0);
        }
        if (to % 2 == 1) {
          if (dsuf[to-1] == dpre[to] && tin <= tpre + suf[to-1]) {
            tin = tpre + suf[to-1];
            tdin = dpre[to];
          }
          if (tin <= in[to-1]) {
            tin = in[to-1];
            tdin = din[to-1];
          }
          tpre = pre[to-1] + (dpre[to-1] == dpre[to] ? tpre : 0);
        }
      }
      if (from != to) {
        if (dsuf[from] == dpre[to] && fin < fsuf + tpre) {
          fin = fsuf + tpre;
          fdin = dsuf[from];
        }
        if (fin < tin) {
          fin = tin;
          fdin = tdin;
        }
      }
      cout << fin << endl;
    }
  }
  return 0;
}

