#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cassert>
#include<set>
#include<bitset>
#include<queue>
#include<cstdlib>
#include<cmath>
#include<iostream>

using namespace std;
const int maxn=1e6+20, maxm=2e3+5, inf=2e9, P=998244353, bs=661;
const double eps=1e-10, pi=3.1415926535897932384;
typedef long long LL;
typedef unsigned long long ULL;
const LL INF=4e18;
typedef pair<LL, int> pli;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
inline int read() {
	int x=0, f=1; char c=getchar();
	for(; c<'0'||c>'9'; c=getchar()) if(c=='-') f=0;
	for(; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';
	return f?x:-x;
}
int a[maxn], nxt[maxn];
int f[maxn][21];
int main() {
	int n=read(), Q=read();
	for(int i=1; i<=n; ++i) 
		a[i]=read();
	int minR=1e9;
	for(int i=1; i<=n; ++i) for(int j=0; j<=20; ++j) f[i][j]=1e9;
	for(int i=n; i; --i) {
		if(nxt[a[i]]>0) {
			minR=min(minR, nxt[a[i]]); 
		}nxt[a[i]]=i;
		f[i][0]=minR;
	}
	for(int i=n; i>0; --i)
		for(int j=1; f[i][j-1]<=n; ++j) 
			f[i][j]=f[f[i][j-1]][j-1];
	printf("%d\n", f[1][0]);
	while(Q--) {
		int l=read(), r=read(); if(l>r) swap(l, r); 
		int t=2*(r-l);
		for(int i=20; i>=0; --i)
			if(f[l][i]<=r) t-=(1<<i), l=f[l][i];
		printf("%d\n", t);
	}
	return 0;
}