#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define pb emplace_back
#define mp make_pair
#define fi first
#define se second
typedef vector<int> vi;
typedef pair<int,int> pi;

namespace IO{
	char buf[1<<25], *iS=buf-1;
	
	void init(){
		fread(buf, 1, 1<<25, stdin);
	}
	#define getchar() (*++iS)
	int read(){
		int res=0;
		char ch=' ';
		do{
			ch=getchar();
		}while(!isdigit(ch));
		do{
			res=res*10+ch-48;
			ch=getchar();
		}while(isdigit(ch));
		return res;
	}
}
using IO::read;

void chmin(int &x,int y){
	if(y<x) x=y;
}

signed main(){
	ios::sync_with_stdio(0);
	
	IO::init();
	
	int n=read(), q=read();
	
	vi a(n+1), lst(n+1), nxt(n+2), mx(n+2);
	vector<vi> bz(__lg(n)+1, vi(n+2));
	
	rep(i,1,n){
		a[i]=read();
	}
	nxt[n]=nxt[n+1]=n+1;
	per(i,n,1){
		nxt[i]=nxt[i+1];
		if(lst[a[i]]){
			chmin(nxt[i], lst[a[i]]);
		}
		lst[a[i]]=i;
	}
	
	bz[0]=nxt;
	rep(i,1,(int)bz.size()-1){
		rep(j,1,n+1){
			bz[i][j]=bz[i-1][bz[i-1][j]];
		}
	}
	per(i,(int)bz.size()-1,0){
		rep(j,1,n+1){
			if(bz[i][j]<=n){
				mx[j]=i;
			}
		}
	}
	
	rep(_,1,q){
		int l=read(), r=read();
		if(l>r){
			swap(l, r);
		}
		int len=r-l;
		int ans=0;
		per(i,mx[l],0){
			if(bz[i][l]<=r){
				ans+= 1<<i;
				l=bz[i][l];
			}
		}
		cout<< len*2-ans <<'\n';
	}
}