#include<iostream>
#include<fstream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<deque>
#include<set>
#include<map>
#include<bitset>
#include<ctime>
#include<queue>
using namespace std;
#define int long long
#define pii pair <int, int>
#define XX first
#define YY second

// constants:
const int mn = 500005;
const int mod = 1000000007;
const long long inf = 4444444444444444444;
const int sminf = 1111111111;
const bool is_multitest = 0;
const bool is_interactive = 0;

// i/o methods:
const bool input_from_file = 0;
const bool output_to_file = 0;
#define filename ""
#define in_extension "inp"
#define out_extension "out"

// data preprocessing: (e.g.: divisor generating, prime sieve)
void preprocess()
{
    
}

// global variables:
int n, q;
vector <int> A;
vector <int> ans;
vector <int> nxt, lst;
vector <pair <pii, int> > queries={{{-1, -1}, 0}};

class fenwick_tree {
public:
    int FW[mn];
    fenwick_tree() {
        for (int i=0; i<mn; i++) FW[i] = 0;
    }

    int get(int u) {
        int ret = 0;
        while (u>0) {
            ret += FW[u];
            u-=(u&(-u));
        }
        return ret;
    }

    void update(int u, int g) {
        while (u<=n) {
            FW[u] += g;
            u+=(u&(-u));
        }
    }

    int get_seg(int l, int r) {
        return get(r) - get(l-1);
    }

} FW1;
// main solution goes here:
void execute(int test_number)
{
    cin>>n>>q;
    A.assign(n+1, 0);
    for (int i=1; i<=n; i++) cin>>A[i];
    int u, v;
    for (int i=1; i<=q; i++) {
        cin>>u>>v;
        queries.push_back({{u, v}, i});
    }
    sort(queries.begin(), queries.end());

    lst.assign(n+1, inf);
    nxt.assign(n+1, inf);
    for (int i=n; i>0; i--) {
        nxt[i] = lst[A[i]];
        lst[A[i]] = i;
    }

    for (int i=1; i<=n; i++) if (lst[i] < inf) FW1.update(lst[i], 1);

    ans.assign(q+1, 0);
    for (int i=1; i<=q; i++) {
        int lstX = max(1ll, queries[i-1].XX.XX);
        int thisX = queries[i].XX.XX;
        for (int i=lstX; i<thisX; i++) {
            FW1.update(i, -1);
            if (nxt[i] < inf) FW1.update(nxt[i], 1);
        }
        ans[queries[i].YY] = FW1.get_seg(thisX, queries[i].XX.YY);
    }

    for (int i=1; i<=q; i++) cout<<ans[i]<<"\n";
}
// REMEMBER TO CHOOSE TEST METHODS
// PLEASE REMOVE cout AND cerr DEBUG LINES BEFORE SUBMITTING PROBLEMS
// Solution by low_



















signed main()
{
#ifdef lowie
    if (!is_interactive)
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
#else
    if (input_from_file) freopen(filename"."in_extension, "r", stdin);
    if (output_to_file) freopen(filename"."out_extension, "w", stdout);
#endif
    if (!is_interactive)
    {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }

    preprocess();
    int ntest;
    if (is_multitest) cin >> ntest;
    else ntest = 1;

    for (int testno = 1; testno <= ntest; testno++)
    // use for instead of while to serve facebook hacker cup test format
    {
        execute(testno); // only start coding in this function, not in main
    }
}
// Template by low_
// Contact me via mail: ttuandung1803@gmail.com
// ...or codeforces: www.codeforces.com/profiles/low_
// ...or if you're interested in food: www.instagram.com/lowie.exe/

Measured memory_bytes: 35100