#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;

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' );
}

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

int lef[MAXN], rig[MAXN];
int tot = 0;

int pos[MAXN];
int stk[MAXN], top = 0;

int col[MAXN];

int N, Q;

inline void Work() {
	top = tot = 0;
	rep( i, 1, N ) stk[i] = pos[i] = 0;
	rep( i, 1, N ) 
		if( pos[col[i]] ) {
			tot ++, lef[tot] = pos[col[i]], rig[tot] = i;
			while( top ) pos[stk[top --]] = 0;
		} else pos[stk[++ top] = col[i]] = i;
	rep( i, 1, Q ) {
		int l = qL[i], r = qR[i];
		if( l > r ) continue;
		ans[i] = 2 * ( r - l );
		int p1 = std :: lower_bound( lef + 1, lef + 1 + tot, l ) - lef,
			p2 = std :: upper_bound( rig + 1, rig + 1 + tot, r ) - rig - 1;
		if( p1 <= p2 ) ans[i] -= p2 - p1 + 1;
	}
}

int main() {
	// freopen( ".in", "r", stdin );
	// freopen( ".out", "w", stdout );
	Read( N ), Read( Q );
	rep( i, 1, N ) Read( col[i] );
	rep( i, 1, Q ) Read( qL[i] ), Read( qR[i] );
	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;
}