#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pir pair<ll,ll>
#define ls first
#define rs second
#define mp make_pair
#define mod
#define MAXN 200010
#define qmod(x) (x>mod?x-mod:x)
inline ll read(){
    ll x = 0,f = 1;
    char c = getchar();
    while(c < '0'||c > '9'){
        if(c == '-')f = -1;
        c = getchar();
    }
    while(c >= '0'&&c <= '9'){
        x = x*10+c-'0';
        c = getchar();
    }
    return x*f;
}
ll a[MAXN];
struct node_sgt_minz{
    ll l[MAXN * 4],r[MAXN * 4],minz[MAXN * 4];
    void push_up(ll now){
        minz[now] = min(minz[now << 1], minz[now << 1 |1]);
    }

    void build(ll lz, ll rz, ll now){
        l[now] = lz;
        r[now] = rz;
        minz[now] = 1e18;
        if(lz == rz){
            minz[now] = a[lz];
            return;
        }
        ll mid = (lz + rz) >> 1;
        build(lz, mid, now << 1);
        build(mid + 1, rz, now << 1 | 1);
        push_up(now);
    }
    ll query(ll lz, ll rz, ll now){
        if(l[now] >= lz && r[now] <= rz){
            return minz[now];
        }
        ll res = 1e18;
        ll mid = (l[now] + r[now]) >> 1;
        if(lz <= mid)res = min(res, query(lz, rz, now << 1));
        if(rz > mid)res = min(res, query(lz, rz, now << 1 |1));
        return res;
    }
}sgt_minz;


struct node_sgt_val{
    ll l[MAXN * 4],r[MAXN * 4],sum[MAXN * 4];
    void build(ll lz, ll rz, ll now){
        l[now] = lz,r[now] = rz;
        if(lz == rz)return;
        ll mid = (lz + rz) >> 1;
        build(lz, mid, now << 1);
        build(mid + 1, rz, now << 1 |1);
    }
    void insert(ll pos, ll now){
        ++ sum[now];
        if(l[now] == r[now])return;
        ll mid = (l[now] + r[now]) >> 1;
        if(pos <= mid)insert(pos, now << 1);
        else insert(pos, now << 1 | 1);
    }
    ll query(ll lz, ll rz, ll now){
        if(l[now] >= lz && r[now] <= rz)return sum[now];
        ll mid = (l[now] + r[now]) >> 1;
        ll res = 0;
        if(lz <= mid)res += query(lz, rz, now << 1);
        if(rz > mid)res += query(lz, rz, now << 1 | 1);
        return res;
    }
}sgt_val;


struct node_qs{
    ll l,r,id,ans;
}qs[MAXN];
bool cmp(node_qs qsa,node_qs qsb){
    return qsa.r < qsb.r;
}

map <ll,ll> t;
ll pre[MAXN],re_id[MAXN];
ll n,q;
int main(){
    freopen("dry.in", "r", stdin);
    freopen("dry.out", "w", stdout);
    n = read(),q = read();
    for(int i = 1;i <= n; ++i)a[i] = read();
    sgt_minz.build(1, n, 1);
    for(int i = 1;i <= n; ++i){
        if(!t[a[i]])pre[i] = 0;
        else{
            ll nxt = t[a[i]];
            if(nxt == i - 1)pre[i] = i - 1;
            else{
                if(sgt_minz.query(nxt + 1,i - 1,1) >= a[i])pre[i] = nxt;
                else pre[i] = 0;
            }
        }
        t[a[i]] = i;
    }
    for(int i = 1;i <= q; ++i){
        qs[i].l = read();
        qs[i].r = read();
        qs[i].id = i;
    }
    // for(int i = 1;i <= n; ++i)cout << pre[i] << " ";
    // cout << endl;
    sort(qs + 1,qs + 1 + q, cmp);
    ll idx = 1;
    sgt_val.build(0, n, 1);
    for(int i = 1;i <= q; ++i){
        while(idx <= qs[i].r){
            sgt_val.insert(pre[idx], 1);
            ++ idx;
        }
        re_id[qs[i].id] = i;
        ll sum = sgt_val.query(qs[i].l, qs[i].r, 1);
        qs[i].ans = (qs[i].r - qs[i].l + 1) - sum;
    }
    for(int i = 1;i <= q; ++i){
        cout << qs[re_id[i]].ans << endl;
    }
    return 0;
}