#include <algorithm>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <time.h>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <numeric>
#include <limits>
#include <type_traits>
#include <locale>
#include <omp.h>

using namespace std;
#define SAY_YES cout << "YES" << endl;
#define SAY_Yes cout << "Yes" << endl;
#define SAY_NO cout << "NO" << endl;
#define SAY_No cout << "No" << endl;
#define IFYES(TRUE_OR_FALSE)   \
    if (TRUE_OR_FALSE)         \
    {                          \
        cout << "YES" << endl; \
    }                          \
    else                       \
    {                          \
        cout << "NO" << endl;  \
    }
#define IFYes(TRUE_OR_FALSE)   \
    if (TRUE_OR_FALSE)         \
    {                          \
        cout << "Yes" << endl; \
    }                          \
    else                       \
    {                          \
        cout << "No" << endl;  \
    }
#define IFyes(TRUE_OR_FALSE)   \
    if (TRUE_OR_FALSE)         \
    {                          \
        cout << "yes" << endl; \
    }                          \
    else                       \
    {                          \
        cout << "no" << endl;  \
    }
#define DEBUG_OUTPUT_ARRAY(XXX, ONE)                            \
    for (int i = 0; i < (ONE); i++)                             \
    {                                                           \
        cout << "DEBUG: i = " << i << " -> " << XXX[i] << endl; \
    }
#define DEBUG_OUTPUT_ARRAY2(XXX, ONE, TWO)                             \
    for (int i = 0; i < (ONE); i++)                                    \
    {                                                                  \
        cout << "<<< i = " << i << " >>>" << endl;                     \
        for (int j = 0; j < (TWO); j++)                                \
        {                                                              \
            cout << "DEBUG: j = " << j << " -> " << XXX[i][j] << endl; \
        }                                                              \
    }
#define DEBUG_OUTPUT_ARRAY2_BOX(XXX, ONE, TWO) \
    for (int i = 0; i < (ONE); i++)            \
    {                                          \
        cout << i << "  ";                     \
        for (int j = 0; j < (TWO); j++)        \
        {                                      \
            cout << XXX[i][j] << " ";          \
        }                                      \
        cout << endl;                          \
    }

typedef pair<long long int, long long int> pll;
typedef pair<long long int, pll> lpll;

const long long int mod = 1000000007;
const long long int INF = 1e18;
const long double PI=3.14159265358979323; 
//const long long int pl=1000000;
long long int N,Q,X,Y,res=0,K,c[500200];
pll RL[500500],memoLR[500500];
map<pll,long long int>mp;
string S;

//セグメント木
class SegmentTree{
    public:
	long long int dataSize,identityElement;
	pair<long long int,long long int>* treeDataRange;
	long long int* treeData;

	//要素数nと単位元e
	SegmentTree(long long int n,long long int e){
		dataSize=2;
		while(dataSize<n){
			dataSize*=2;
		}
		identityElement=e;
		treeData=new long long int [2*dataSize+1];
		treeDataRange=new pair<long long int,long long int> [2*dataSize+1];
		for(int i=dataSize;i<2*dataSize;i++){
			treeDataRange[i]={i-dataSize,i-dataSize+1};
		}
		for(int i=dataSize-1;i>=1;i--){
			treeDataRange[i]={treeDataRange[2*i].first,treeDataRange[2*i+1].second};
		}
		for(int i=1;i<2*dataSize;i++){
			treeData[i]=e;
		}
	}

    long long int DataChange(long long int id,long long int data){
        treeData[id+dataSize]=data;
        DataChangeLoop((id+dataSize)/2);
		return 0;
    }
    long long int DataChangeLoop(long long int id){
        treeData[id]=Calculation(treeData[2*id],treeData[2*id+1]);
        if(id==1){return 0;}
        DataChangeLoop(id/2);
        return 0;
    }

	long long int Calculation(long long int x,long long int y){
		return x+y;
	}
	//[l,r)の結果を出力
	long long int OutPut(long long int l,long long int r){
		return OutPutLoop(1,l,r);
	}
	
	long long int OutPutLoop(long long int now,long long int l,long long int r){
		
		if(l>=r){return identityElement;}

        if(l==treeDataRange[now].first&&r==treeDataRange[now].second){return treeData[now];}

		return Calculation(OutPutLoop(2*now,l,min(treeDataRange[2*now].second,r)),OutPutLoop(2*now+1,max(treeDataRange[2*now+1].first,l),r));
		
	}
};

long long int lastAppend[500500]={},beforelastAppend[500500];
SegmentTree SEG(500500,0);
int main(){

    cout << fixed << setprecision(18);
    cin>>N>>Q;
    for(long long int i = 0; i < N; i++){
        cin>>c[i];
        c[i]--;
    }
    for(long long int i = 0; i < Q; i++){
        cin>>RL[i].second>>RL[i].first;
        RL[i].first--;
        RL[i].second--;
        memoLR[i]={RL[i].second,RL[i].first};
    }
    sort(RL,RL+Q);
    for(long long int i = 0; i < N; i++){
        lastAppend[i]=-1;
    }
    long long int R=-1;
    for(long long int i = 0; i < Q; i++){
        for(long long int j = RL[i].first; j >=R+1; j--){
            if(lastAppend[c[j]]>=j){continue;}
            SEG.DataChange(j,SEG.treeData[SEG.dataSize+j]+1);
            if(lastAppend[c[j]]!=-1)SEG.DataChange(lastAppend[c[j]],SEG.treeData[SEG.dataSize+lastAppend[c[j]]]-1);
            lastAppend[c[j]]=j;
        }
        R=RL[i].first;
        mp[{RL[i].second,RL[i].first}]=SEG.OutPut(RL[i].second,RL[i].first+1);
        

    }
    for(long long int i = 0; i < Q; i++){
        cout<<mp[memoLR[i]]<<'\n';
    }
}



Measured memory_bytes: 83120