#include<bits/stdc++.h>
using namespace std;const int N=1e6+5;int n,q,vi[N],fa[N],f[N],ans[N];vector<int>v[N];vector<pair<int,int>>s[N]; 
#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),(iS==iT?EOF:*iS++)):*iS++)
namespace IO{const int SIZE=(1<<21)+1;char ibuf[SIZE],*iS,*iT,obuf[SIZE],*oS=obuf,*oT=oS+SIZE-1,c,qu[55];int f,qr;
	inline void flush(){fwrite(obuf,1,oS-obuf,stdout),oS=obuf,fflush(stdout);}inline void putc(char x){*oS++=x;if(oS==oT)flush();}
	template<class I>inline void read(I &x){for(f=1,c=gc();c<'0'||c>'9';c=gc())if(c=='-')f=-1;for(x=0;c<='9'&&c>='0';c=gc())x=x*10+(c&15);x*=f;}
	template<class I>inline void print(I x){if(!x)putc('0');if(x<0)putc('-'),x=-x;while(x)qu[++qr]=x%10+'0',x/=10;while(qr)putc(qu[qr --]);}
	struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}using IO::read;using IO::putc;using IO::print;
void cal(int u){if(fa[u]==u)return;f[u]+=f[fa[u]],fa[u]=fa[fa[u]];}
int main(){//freopen("color.in","r",stdin),freopen("color.out","w",stdout);
	read(n),read(q);for(int x,lst=0,i=1;i<=n;i++)read(x),lst=max(lst,vi[x]),v[lst].push_back(i),vi[x]=i;
	for(int x,y,i=1;i<=q;i++){read(x),read(y);if(x>y)swap(x,y);s[x].push_back({y,i});}
	for(int i=n;i;i--){fa[i]=i;for(auto j:v[i])f[j]=1,fa[j]=i;
		for(auto j:s[i])cal(j.first),ans[j.second]=2*(j.first-i)-f[j.first];
	}for(int i=1;i<=q;i++)print(ans[i]),putc('\n');
}