#include <bits/stdc++.h>
#define rep(i, f, t) for(int i(f); i <= t; ++i)
#define re(i, t) for(int i(1); i <= t; ++i)
#define per(i, t, f) for(int i(t); i >= f; --i)
#define pe(i, t) for(int i(t); i >= 1; --i)
#define nx(i, u) for(int i(head[u]); i; i = e[i].nxt)
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
// #define int long long
using namespace std;
typedef pair <int, int> pii;
#define pb push_back
#define fi first
#define se second
#define ix(l, r) ((l + r) | (l != r))
#define ls (ix(l, mid))
#define rs (ix(mid + 1, r))
#define mp(i, j) (make_pair(i, j))
#define inf (int)(1e9+7)
#define INF 0x3f3f3f3f3f3f3f3f
#define eps 1e-10
#define look_memory cerr<<abs(&sT-&eD)/1024.0/1024<<'\n'
bool sT;


namespace IO {
char buf[1 << 21], *p1 = buf, *p2 = buf, buf1[1 << 21];
inline char gc() {
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}

#ifndef ONLINE_JUDGE
#endif

// #define gc getchar

template<class I>
inline void read(I &x) {
    x = 0;
    I f = 1;
    char c = gc();
    while (c < '0' || c > '9') {
        if (c == '-')
            f = -1;
        c = gc();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = gc();
    }
    x *= f;
}

template<class I>
inline void write(I x) {
    if (x == 0) {
        putchar('0');
        return;
    }
    I tmp = x > 0 ? x : -x;
    if (x < 0)
        putchar('-');
    int cnt = 0;
    while (tmp > 0) {
        buf1[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0)
        putchar(buf1[--cnt]);
}

#define in(x) read(x)
#define outn(x) write(x), putchar('\n')
#define out(x) write(x), putchar(' ')

} using namespace IO;

const int N = 1e6 + 5;
int n, Q, l, r, ans;
int a[N], b[N]; 

int main () {
    read(n),read(Q);
    re(i, n) read(a[i]);
    while(Q--) {
        read(l), read(r);
        ans = inf;
        if(l <= r) {
            int L = l;
            rep(i, l, r) {
                if(a[i] != a[l]) {
                    L = i-1;
                    break;
                } 
            }
            rep(i, L, r) {
                ++b[a[i]];
                ans = min(ans, (r-L+1)-b[a[i]]);
            }
        }
        else {
            swap(l, r);
            int R = r;
            per(i, r, l) {
                if(a[i] != a[r]) {
                    R = i+1;
                    break;
                } 
            }
            rep(i, l, R) {
                ++b[a[i]];
                ans = min(ans, (R-l+1)-b[a[i]]);
            }
        }
        rep(i, l, r) b[a[i]] = 0;
        outn(ans + r - l);
    }
    return 0;
}