#include <bits/stdc++.h> 
using namespace std; 
#define ll long long   
#define mp make_pair
#define pb push_back
#define se second
#define fi first 
void solve() {
    ll i, j, k, l, test, n, q, x, y, z;
    cin>>test;
    while(test--) {
        cin>>n;
        //for(i=0;i<n-1;i++) cout<<9;
            //cout<<"8\n";
        if(n%4==0) {
            for(i=0;i<n-n/4;i++) cout<<9;
            for(i=0;i<n/4;i++) cout<<8;
            cout<<"\n";
        }
        else {
            for(i=0;i<n-n/4-1;i++) cout<<9;
            for(i=0;i<n/4+1;i++) cout<<8;
            cout<<"\n";
        }
    }
}

void merge(vector<int> tree[],  
                 int treeNode) 
{ 
    int len1 =  
      tree[2 * treeNode].size(); 
    int len2 =  
      tree[2 * treeNode + 1].size(); 
    int index1 = 0, index2 = 0;  
    while (index1 < len1 && index2 < len2) {  
        if (tree[2 * treeNode][index1] >  
              tree[2 * treeNode + 1][index2]) { 
  
            tree[treeNode].push_back( 
                tree[2 * treeNode + 1][index2] 
                ); 
            index2++; 
        } 
        else { 
            tree[treeNode].push_back( 
                tree[2 * treeNode][index1] 
                ); 
            index1++; 
        } 
    }  
    while (index1 < len1) { 
        tree[treeNode].push_back( 
            tree[2 * treeNode][index1] 
            ); 
        index1++; 
    }  
    while (index2 < len2) { 
        tree[treeNode].push_back( 
            tree[2 * treeNode + 1][index2] 
            ); 
        index2++; 
    } 
    return; 
} 
void build(vector<int> tree[],  
    int* arr, int start, int end,  
                  int treeNode) 
{  
    if (start == end) { 
        tree[treeNode].push_back( 
            arr[start]); 
        return; 
    } 
    int mid = (start + end) / 2;  
    build(tree, arr, start,  
          mid, 2 * treeNode);  
    build(tree, arr, mid + 1, end,  
                 2 * treeNode + 1); 
    merge(tree, treeNode); 
    return; 
} 

int query(vector<int> tree[],  
     int treeNode, int start, int end,  
            int left, int right) 
{ 
 
    if (start > right || end < left) { 
        return 0; 
    } 

    if (start >= left && end <= right) { 
 
        return tree[treeNode].end() -  
          upper_bound(tree[treeNode].begin(),  
            tree[treeNode].end(), right); 
    } 
  
    int mid = (start + end) / 2;  
    int op1 = query(tree, 2 * treeNode,  
              start, mid, left, right);  
    int op2 = query(tree, 2 * treeNode + 1,  
            mid + 1, end, left, right); 
    return op1 + op2; 
}  
vector<int> tree[20*100000+7]; 
ll  arr[500007];
int main() 
{ 
    #ifndef ONLINE_JUDGE
        freopen("input1.txt", "r", stdin);
        freopen("output1.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
  
    ll n, q; 
    cin>>n>>q;
    for(ll i=0;i<n;i++) cin>>arr[i];
  
    int next_right[n]; 
    
  
    unordered_map<int, int> ump; 
    for (int i = n - 1; i >= 0; i--) { 
        if (ump[arr[i]] == 0) { 
            next_right[i] = n; 
            ump[arr[i]] = i; 
        } 
        else { 
            next_right[i] = ump[arr[i]]; 
            ump[arr[i]] = i; 
        } 
    }  
    build(tree, next_right, 0, n - 1, 1); 
  
    ll ans; 
    ll left1, right1;
    while(q--) {
        cin>>left1>>right1;
        ans = query(tree, 1, 0, n - 1,  
                  left1-1, right1-1); 
        cout << ans << "\n"; 
    }
}

Measured memory_bytes: 142080