#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define fi first
#define se second
#define eb emplace_back
#define bp __builtin_parity
#define y1 yyl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef bitset<509> bset;
typedef pair<bset,bset> v2;

int read() {
	int x=0,w=1; char c=getchar();
	while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
	while(isdigit(c)) {x=x*10+c-'0'; c=getchar();}
	return x*w;
}

const int N=1e6+9;
int n,Q,a[N];

struct Jump {
	int t[21][N],a[N],cnt[N];
	void init(int *b) {
		rep(i,1,n) a[i]=b[i];
		int j=n; t[0][n+1]=n+1;
		per(i,n,1) {
			cnt[a[i]]++;
			if(cnt[a[i]]>1) {
				while(a[j]!=a[i]) j--;
				cnt[a[i]]--, t[0][i]=j, j--;
			} else t[0][i]=t[0][i+1];
		}
		rep(h,1,20) {
			rep(i,1,n) t[h][i]=t[h-1][t[h-1][i]];
		}
	}
	int qry(int l,int r) {
		int res=0;
		int u=l;
		per(h,20,0) if(t[h][u]&&t[h][u]<=r) u=t[h][u], res|=(1<<h);
		return res;
	}
} toright, toleft;

signed main() {
	n=read(), Q=read();
	rep(i,1,n) a[i]=read();
	toright.init(a);
	reverse(a+1,a+n+1);
	toleft.init(a);
	rep(i,1,Q) {
		int l=read(), r=read();
		if(l<=r) printf("%d\n",(r-l)*2-toright.qry(l,r));
		else printf("%d\n",(l-r)*2-toleft.qry(n-l+1,n-r+1));
	}
	return 0;
}