#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline char getc() { //Don't use it in interactive problems!!!
	static char *p1, *p2, buf[1<<23];
	return p1==p2?(p2=(p1=buf)+fread(buf, 1, 1<<23, stdin), p1==p2?EOF:*p1++):*p1++;
}
inline int read() {
	int f=1, r=0; char c=getc();
	while (!isdigit(c)) f^=c=='-', c=getc();
	while (isdigit(c)) r=r*10+c-48, c=getc();
	return f?r:-r;
}
#define fi first
#define se second
template<class T> inline void ckmin(T &x, T y) {if (y<x) x=y;}
template<class T> inline void ckmax(T &x, T y) {if (x<y) x=y;}
const int N=1e6+7;
int n, m, Q, lst[N], jp[N][20], L[N], R[N];
struct seg {
	int l, r;
	seg(int _l=0, int _r=0) :l(_l), r(_r) {}
} a[N], b[N];
int main() {
#ifndef ONLINE_JUDGE
	freopen("1.in", "r", stdin);
	freopen("1.out", "w", stdout);
#endif
	n=read(), Q=read();
	for (int i=1; i<=n; i++) {
		int x=read();
		if (lst[x]) b[++m]={lst[x], i-1};
		lst[x]=i;
	}
	int _m=0;
	for (int i=1; i<=m; i++) if (b[i].l>a[_m].l) a[++_m]=b[i];
	m=_m;
	for (int i=n, p=m+1; i; i--) {
		if (a[p-1].l==i) p--;
		L[i]=p;
	}
	for (int i=1, p=0; i<=n; i++) {
		if (a[p+1].r==i) p++;
		R[i]=p;
	} 
	int lg=m?__lg(m):0;
	for (int i=0; i<=lg; i++) jp[m+1][i]=m+1;
	for (int i=m; i; i--) {
		jp[i][0]=L[a[i].r+1];
		for (int j=1; j<=lg; j++) jp[i][j]=jp[jp[i][j-1]][j-1];
	}
	while (Q--) {
		int l=read(), r=read(); if (l>r) swap(l, r);
		int ans=2*(r-l), p=L[l], ed=R[r-1];
		if (p<=ed) {
			ans--;
			for (int j=lg; ~j; j--)
				if (jp[p][j]<=ed) ans-=1<<j, p=jp[p][j];
		}
		printf("%d\n", ans);
	}
	return 0;
}