#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 b[N];

struct Work {

    int a[N];
    int st[20][N];
    int lst[N], nxt[N];

    void init () {
        int mn = inf;
        rep(i, 0, 19) re(j, n) st[i][j] = inf;
        pe(i, n) {
            nxt[i] = n + 1;
            if(lst[a[i]]) { 
                nxt[i] = lst[a[i]];
            }
            mn = min(mn, nxt[i]);
            st[0][i] = mn;
            lst[a[i]] = i;
        } 
        re(i, 19) {
            re(j, n-(1<<i)+1) {
                if(st[i-1][j] >= n) break;
                st[i][j] = st[i-1][st[i-1][j]+1];
            }
        } 
    }

    int solve (int l, int r) {
        int ans = r - l;
        int now = l;
        per(i, 19, 0) {
            if(st[i][now] <= r) {
                now = st[i][now] + 1; 
                ans -= (1 << i);
            }
            if(now > n) break;
        }
        return ans;
    }

}T[2];

int main () {
    read(n),read(Q);
    re(i, n) {
        read(b[i]);
        T[0].a[i] = b[i];
        T[1].a[n-i+1] = b[i];
    }
    rep(i, 0, 1) T[i].init();
    while(Q--) {
        read(l), read(r);
        int ans = 0;
        if(l <= r) {
            ans = T[0].solve(l, r);
        }
        else { 
            ans = T[1].solve(n-l+1, n-r+1);
            swap(l, r);
        }
        outn(ans + r - l); 
    }
    return 0;
}