using namespace std;
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <assert.h>
#include <functional>

typedef long long ll;

//BIT from https://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/

/*         n --> No. of elements present in input array.
    BITree[0..n] --> Array that represents Binary Indexed Tree.
    arr[0..n-1] --> Input array for which prefix sum is evaluated. */

    // Returns sum of arr[0..index]. This function assumes 
    // that the array is preprocessed and partial sums of 
    // array elements are stored in BITree[]. 
long long getSum(long long BITree[], long long index)
{
    long long sum = 0; // Iniialize result 

    // index in BITree[] is 1 more than the index in arr[] 
    index = index + 1;

    // Traverse ancestors of BITree[index] 
    while (index > 0)
    {
        // Add current element of BITree to sum 
        sum += BITree[index];

        // Move index to parent node in getSum View 
        index -= index & (-index);
    }
    return sum;
}

// Updates a node in Binary Index Tree (BITree) at given index 
// in BITree. The given value 'val' is added to BITree[i] and  
// all of its ancestors in tree. 
void updateBIT(long long BITree[], long long n, long long index, long long val)
{
    // index in BITree[] is 1 more than the index in arr[] 
    index = index + 1;

    // Traverse all ancestors and add 'val' 
    while (index <= n)
    {
        // Add 'val' to current node of BI Tree 
        BITree[index] += val;

        // Update index to that of parent in update View 
        index += index & (-index);
    }
}

// Constructs and returns a Binary Indexed Tree for given 
// array of size n. 
long long* constructBITree(long long n)
{
    // Create and initialize BITree[] as 0 
    long long* BITree = new long long[n + 1];
    for (long long i = 1; i <= n; i++)
        BITree[i] = 0;


    return BITree;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    long long n, q;
    cin >> n >> q;
    vector<long long> vals;
    vector<long long> last_seen(n+1, -1);
    for (long long i = 0; i < n; i++) {
        long long c;
        cin >> c;
        vals.push_back(c);
    }

    
    vector<pair<pair<long long, long long>, long long>> qs;
    long long* BIT = constructBITree(q + 1);
    for (long long i = 0; i < q; i++) {
        long long x, y;
        cin >> x >> y;
        x--;
        y--;
        qs.push_back({ {x, y}, i });
    }
    sort(qs.begin(), qs.end());
    vector<vector<long long> > timesup(n+1);
    for (long long i = 0; i < q; i++) {
        timesup[qs[i].first.second].push_back(i);
    }
    long long care = 0;
    vector<long long> ans(q);
    vector<long long> whatwecaredabout;
    for (long long i = 0; i < n; i++) {
        while (care + 1 < qs.size() && qs[care + 1].first.first <= i) care++;
        
        whatwecaredabout.push_back(care);
        if (last_seen[vals[i]] == -1) {
            updateBIT(BIT, q+1, 0, 1);
            updateBIT(BIT, q + 1, care+1, -1);
        }
        else {
            updateBIT(BIT, q + 1, whatwecaredabout[last_seen[vals[i]]] + 1, 1);
            updateBIT(BIT, q + 1, care + 1, -1);
        }
        last_seen[vals[i]] = i;
        for (long long qi : timesup[i]) {
            ans[qs[qi].second] = getSum(BIT, qi);
        }
    }
    for (long long a : ans) {
        cout << a << endl;
    }
}

Measured memory_bytes: 60888