#include <cstdio>
#include <algorithm>

#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )

const int MAXN = 1e6 + 5, MAXLOG = 25;

template<typename _T>
inline void Read( _T &x ) {
	x = 0; char s = getchar(); bool f = false;
	while( ! ( '0' <= s && s <= '9' ) ) { f = s == '-', s = getchar(); }
	while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar(); }
	if( f ) x = -x;
}

template<typename _T>
inline void Write( _T x ) {
	if( x < 0 ) putchar( '-' ), x = -x;
	if( 9 < x ) Write( x / 10 );
	putchar( x % 10 + '0' );
}

template<typename _T>
inline _T Min( const _T &a, const _T &b ) {
	return a < b ? a : b;
}

int nxt[MAXLOG][MAXN], pos[MAXN];
int lg2[MAXN];

int qL[MAXN], qR[MAXN];
int ans[MAXN];

int col[MAXN];

int N, Q;

inline void Work() {
	rep( i, 1, N ) pos[i] = N + 1;
	nxt[0][N + 1] = N + 1;
	per( i, N, 1 ) {
		nxt[0][i] = Min( nxt[0][i + 1], pos[col[i]] );
		pos[col[i]] = i;
	}
	for( int j = 1 ; j <= lg2[N] ; j ++ )
		for( int i = 1 ; i + ( 1 << j ) <= N ; i ++ )
			nxt[j][i] = nxt[j - 1][nxt[j - 1][i]];
	rep( i, 1, Q ) {
		int l = qL[i], r = qR[i];
		if( l > r ) continue;
		ans[i] = 2 * ( r - l );
		for( int k = lg2[r - l] ; k >= 0 ; k -- )
			if( l + ( 1 << k ) <= r && nxt[k][l] <= r )
				ans[i] -= 1 << k, l = nxt[k][l];
	}
}

int main() {
	Read( N ), Read( Q );
	rep( i, 1, N ) Read( col[i] );
	rep( i, 1, Q ) Read( qL[i] ), Read( qR[i] );
	lg2[0] = -1; rep( i, 1, N ) lg2[i] = lg2[i >> 1] + 1;
	Work();
	std :: reverse( col + 1, col + 1 + N );
	rep( i, 1, Q ) qL[i] = N - qL[i] + 1, qR[i] = N - qR[i] + 1;
	Work();
	rep( i, 1, Q ) Write( ans[i] ), putchar( '\n' );
	return 0;
}