#include<bits/stdc++.h>
#define ONLINE_JUDGE 1

using namespace std;

namespace IO {
	const int N = (1 << 21);
	char ibuf[N], *p1= ibuf, *p2 = ibuf;
	char obuf[N], *p3 = obuf, ch[100];
	#ifdef ONLINE_JUDGE
		#define getch() (p1 == p2 ? p2 = (p1 = ibuf) + fread(ibuf, 1, N, stdin), (p1 == p2 ? EOF : *p1++) : *p1++)
		inline void putch(const char& ch) {	((p3 - obuf) < N) ? (*p3++ = ch) : (fwrite(obuf, 1, p3 - obuf, stdout), p3 = obuf, *p3++ = ch); }
	#else
		#define getch() getchar()
		inline void putch(const char &ch) { putchar(ch); }
	#endif
	template <typename T> inline void read(T& x) {
		char ch = getch(); x = 0;
		while(!isdigit(ch)) ch = getch();
		while(isdigit(ch)) x = x * 10 + ch - 48, ch = getch();
	}
	template <typename T, typename ...Args> void read(T& x, Args& ...args) {
		read(x), read(args...);
	}
	inline void write(const char &x) {
		putch(x);
	}
	inline void write(const char *s) {
		for(const char *ch = s; *ch; ch++) putch(*ch);
	}
	template <typename T> inline void write(T x) { 
		int top(0);
		do ch[++top] = x % 10 + 48, x /= 10; while(x);
		while(top) putch(ch[top--]);
	}
	template <typename T, typename ...Args> void write(T x, Args ...args) {
		write(x), write(args...);
	}
	inline void flush() { fwrite(obuf, 1, p3 - obuf, stdout); p3 = obuf; }
	#undef getch
}
using IO::read; using IO::write; using IO::putch; using IO::flush;
const int N = 1e6 + 5;

int n, QWQ;
int lst[N], p[N][21];

signed main() {
//	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	freopen("color.in", "r", stdin);
	freopen("color.out", "w", stdout);
	
	read(n, QWQ);
	for(int i = 1, a; i <= n; i++) {
		read(a);
		p[i][0] = max(p[i - 1][0], lst[a]);
		for(int j = 1; p[i][j] = p[p[i][j - 1]][j - 1]; j++) ;
		lst[a] = i;
	}
	for(int l, r, ans; QWQ--; ) {
		read(l, r); 
		if(l == r) { write("0\n"); continue; }
		if(l > r) l ^= r ^= l ^= r;
		ans = (r - l) << 1;
		for(int i = 20; i >= 0; i--) if(p[r][i] >= l) r = p[r][i], ans -= (1 << i);
		write(ans, '\n');
	}
	flush();
	
	return 0;
}