#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a,x) for (auto& a : x)

#define sz(x) (int)(x).size()
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert

const ll SZ = 262144;
ll seg[2*SZ];

void update(int p) {
    for (seg[p += SZ] = 1; p > 1; p >>= 1)
        seg[p>>1] = seg[(p|1)^1] + seg[p|1];
}

ll query(int l, int r) {
    ll resL = 0, resR = 0; r++;
    for (l += SZ, r += SZ; l < r; l >>= 1, r >>= 1) {
        if (l&1) resL += seg[l++];
        if (r&1) resR += seg[--r];
    }
    return resL + resR;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
    int N, Q; cin >> N >> Q;
    int A[N]; F0R(i, N) cin >> A[i];
    F0R(i, N) A[i]--;
    vector<pi> when;
    bool inStack[N]; F0R(i, N) inStack[i] = false;
    int lst[N]; F0R(i, N) lst[i] = -1;
    stack<int> cur;
    F0R(i, N) {
        if (inStack[A[i]]) {
            when.pb({lst[A[i]]+1, i});
        } else {
            when.pb({0, i});
        }
        lst[A[i]] = i;
        while (!cur.empty() && cur.top() > A[i]) {
            inStack[cur.top()] = false; cur.pop();
        }
        if (cur.empty() || cur.top() != A[i]) {
            cur.push(A[i]); inStack[A[i]] = true;
        }
    }

    int p = 0;
    vector<pair<pi, int>> qs;
    F0R(i, Q) {
        int X, Y; cin >> X >> Y; X--; Y--;
        qs.pb({{X, Y}, i});
    }
    int ans[Q];
    sort(all(qs));
    sort(all(when));
    trav(a, qs) {
        while (p < sz(when) && when[p].f <= a.f.f) {
            update(when[p].s);
            p++;
        }
        ans[a.s] = query(a.f.f, a.f.s);
    }

    F0R(i, Q) {
        cout << ans[i] << endl;
    }
	return 0;
}