#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
// 293206GT
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <unordered_set>
#include <stack>
#include <string>
#include<algorithm>
#include <random>
#include <bitset>
#include <chrono>

typedef long long ll;
//#define int ll
using namespace std;
#define put(a) cout << (a) << '\n'
#define sqr(x) ((x) * (x))
typedef pair<int, int> pii;
typedef long double ld;
typedef pair<ld, ld> pld;
typedef unsigned long long ull;

typedef vector<int> vi;
typedef vector<pii> vpii;
#define rep(x, y, a) for (int x = (y); x < (int)(a); ++x)
#define all(a) a.begin(), a.end()
#define chkmax(a, b) a = max(a, (b))
#define chkmin(a, b) a = min(a, (b))
#define prev asasdasd
#define next aasdasda
#define left asdasdasdasd
#define right asnabsdkasdl
#define rank asdasdknlasd
#define move asdasdas
#define fname "parray"
#define fin fname".in"
#define fout fname".out"
#define files freopen(fin, "r", stdin);freopen(fout, "w", stdout);
namespace IO {

    template<class A, class B>
    ostream &operator<<(ostream &out, vector<pair<A, B>> a);

    template<class A>
    ostream &operator<<(ostream &out, vector<A> a);

    template<class A, class B>
    ostream &operator<<(ostream &out, pair<A, B> a) {
        out << a.first << " " << a.second;
        return out;
    }

    template<class A, class B>
    ostream &operator<<(ostream &out, vector<pair<A, B>> a) {
        for (pair<A, B> x: a)
            out << x.first << " " << x.second << '\n';
        return out;
    }

    template<class A>
    ostream &operator<<(ostream &out, vector<A> a) {
        for (A x: a) out << x << ' ';
        return out;
    }

    template<class A, class B>
    istream &operator>>(istream &in, pair<A, B> &a) {
        in >> a.first >> a.second;
        return in;
    }

    template<class A>
    istream &operator>>(istream &in, vector<A> &a) {
        for (A &x: a) in >> x;
        return in;
    }
}
using namespace IO;


mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct fenwick {
    vi tree;
    fenwick(vi a) {
        tree.resize(a.size(), 0);
        rep(i, 0, a.size()) incr(i, a[i]);
    }
    void incr(int i, int x) {
        for (;i < tree.size(); i |= i + 1)tree[i] += x;
    }
    int sum(int r) { // ]
        int res = 0;
        while (r >= 0) {
            res += tree[r];
            r = (r&(r + 1)) - 1;
        }
        return res;
    }
    int get(int l, int r) { // []
        return sum(r) - sum(l - 1);
    }
};
void solve() {
    int n, q;
    cin >> n >> q;
    vi c(n);
    cin >> c;
    vi pos(n + 1, -1);
    vi arr(n);
    rep(i, 0, n) {
        if (pos[c[i]] != -1)arr[pos[c[i]]] = i;
        pos[c[i]] = i;
    }
    rep(i, 0, n) if (arr[i] == 0) arr[i] = n;
    vector<vpii> l_q(n + 1);
    vector<vi> r_q(n + 1);
    rep(tt, 0, q) {
        int l, r;
        cin >> l >> r;
        --l;
        l_q[l].push_back({r - 1, tt});
        r_q[r].push_back(tt);
    }
    vi res(q, 0);
    fenwick fen(vi(n + 1, 0));
    rep(i, 0, n) {
        for (pii x: l_q[i]) {
            res[x.second] -= i - fen.sum(x.first);
        }
        for (int x: r_q[i]) {
            res[x] += i - fen.sum(i - 1);
        }
        fen.incr(arr[i], 1);
    }
    for (int x: r_q[n]) {
        res[x] += n - fen.sum(n - 1);
    }
    rep(i, 0 ,q) put(res[i]);
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(30);
//    freopen("input.txt", "r", stdin);
//    files
    int q = 1;
//    cin >> q;
    while (q--) solve();
}



Measured memory_bytes: 56940