unittest
{
	assert( [ "4 3", "1 2 1 3", "1 3", "2 4", "3 3" ].solve == "2\n3\n1" );
	assert( [ "10 10", "2 5 6 5 2 1 7 9 7 2", "5 5", "2 4", "6 7", "2 2", "7 8", "7 9", "1 8", "6 9", "8 10", "6 8" ].solve == "1\n2\n2\n1\n2\n2\n6\n3\n3\n3" );
	
	assert( [ "4 3", "4 2 1 3", "1 3", "2 4", "3 3" ].solve == "3\n3\n1" );		// 追加ケース
}



import std.algorithm;
import std.conv;
import std.format;
import std.range;
import std.stdio;

void main()
{
	stdin.byLineCopy.solve.writeln;
}

auto solve( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto n = 0L;
	auto q = 0L;
	input.front.formattedRead!"%s %s"( n, q );
	input.popFront;
	auto cs = input.front.split.to!( long[] );
	auto lris = new long[ 3 ][ q ];
	foreach( i, ref lri; lris )
	{
		input.popFront;
		lri = input.front.split.to!( long[] ) ~ i.signed;
		lri[ 0 ]--;
	}
	
	// クエリを右端基準で昇順ソート
	lris.sort!( ( a, b ) => a[ 1 ] < b[ 1 ] );
	
	// 区間[0,r)について、色ごとに最後に現れた場所をメモる
	auto anss = new long[ q ];
	auto bit = BinaryIndexedTree( 1 + n );
	auto as = new long[ 1 + n ];
	as[] = -1;
	auto r = 0L;
	foreach( lri; lris )
	{
		for( ; r < lri[ 1 ]; r++ )
		{
			// 同じ色が一つ前に現れた場所を削除（区間和で同じ色を複数カウントしないようにする）
			if( 0 <= as[ cs[ r ] ] ) bit.add( as[ cs[ r ] ], -1 );
			
			// この色が最後に現れた場所を更新
			as[ cs[ r ] ] = r;
			bit.add( r, 1 );
		}
		
		// 区間[l,r)の色の種類の和を計算
		anss[ lri[ 2 ] ] = bit.sum( lri[ 0 ], lri[ 1 ] );
	}
	return anss.to!( string[] ).join( "\n" );
}

// BIT
struct BinaryIndexedTree
{
	long n;
	long[] ts;
	
	this( long n )
	{
		this.n = n;
		ts = new long[ 1 + n ];
	}
	
	void add( long i, long v )
	{
		for( auto j = i + 1; j < ts.length; j += j & -j ) ts[ j ] += v;
	}
	
	auto get( long i )
	{
		return sum( i, i + 1 );
	}
	
	auto sum( long l, long r )
	{
		auto lt = 0L;
		auto rt = 0L;
		for( auto j = l; 0 < j; j -= j & -j ) lt += ts[ j ];
		for( auto j = r; 0 < j; j -= j & -j ) rt += ts[ j ];
		return rt - lt;
	}
	
	auto length()
	{
		return n;
	}
	
	auto toString()
	{
		auto as = new long[ n ];
		foreach( i, ref a; as ) a = get( i );
		return format( "BIT(%s)", as );
	}
}
