// Program to compute no. of different elements 
// of ranges for different range queries 
#include <bits/stdc++.h> 
using namespace std; 
#define Fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
// Used in frequency array (maximum value of an 
// array element). 
const int MAX = 1000000; 

// Variable to represent block size. This is made 
// global so compare() of sort can use it. 
int block; 

// Structure to represent a query range and to store 
// index and result of a particular query range 
struct Query { 
	int L, R, index, result; 
}; 

// Function used to sort all queries so that all queries 
// of same block are arranged together and within a block, 
// queries are sorted in increasing order of R values. 
bool compare(Query x, Query y) 
{ 
	// Different blocks, sort by block. 
	if (x.L / block != y.L / block) 
		return x.L / block < y.L / block; 

	// Same block, sort by R value 
	return x.R < y.R; 
} 

// Function used to sort all queries in order of their 
// index value so that results of queries can be printed 
// in same order as of input 
bool compare1(Query x, Query y) 
{ 
	return x.index < y.index; 
} 

// calculate distinct elements of all query ranges. 
// m is number of queries n is size of array a[]. 
void queryResults(int a[], int n, Query q[], int m) 
{ 
	// Find block size 
	block = (int)sqrt(n); 

	// Sort all queries so that queries of same 
	// blocks are arranged together. 
	sort(q, q + m, compare); 

	// Initialize current L, current R and current 
	// different elements 
	int currL = 0, currR = 0; 
	int curr_Diff_elements = 0; 

	// Initialize frequency array with 0 
	int freq[MAX] = { 0 }; 

	// Traverse through all queries 
	for (int i = 0; i < m; i++) { 
		
		// L and R values of current range 
		int L = q[i].L, R = q[i].R; 

		// Remove extra elements of previous range. 
		// For example if previous range is [0, 3] 
		// and current range is [2, 5], then a[0] 
		// and a[1] are subtracted 
		while (currL < L) { 
			
			// element a[currL] is removed 
			freq[a[currL]]--; 
			if (freq[a[currL]] == 0) 
				curr_Diff_elements--; 
			
			currL++; 
		} 

		// Add Elements of current Range 
		// Note:- during addition of the left 
		// side elements we have to add currL-1 
		// because currL is already in range 
		while (currL > L) { 
			freq[a[currL - 1]]++; 

			// include a element if it occurs first time 
			if (freq[a[currL - 1]] == 1) 
				curr_Diff_elements++; 
			
			currL--; 
		} 
		while (currR <= R) { 
			freq[a[currR]]++; 

			// include a element if it occurs first time 
			if (freq[a[currR]] == 1) 
				curr_Diff_elements++; 
			
			currR++; 
		} 

		// Remove elements of previous range. For example 
		// when previous range is [0, 10] and current range 
		// is [3, 8], then a[9] and a[10] are subtracted 
		// Note:- Basically for a previous query L to R 
		// currL is L and currR is R+1. So during removal 
		// of currR remove currR-1 because currR was 
		// never included 
		while (currR > R + 1) { 

			// element a[currL] is removed 
			freq[a[currR - 1]]--; 

			// if occurrence of a number is reduced 
			// to zero remove it from list of 
			// different elements 
			if (freq[a[currR - 1]] == 0) 
				curr_Diff_elements--; 
			
			currR--; 
		} 
		q[i].result = curr_Diff_elements; 
	} 
} 

// print the result of all range queries in 
// initial order of queries 
void printResults(Query q[], int m) 
{ 
	sort(q, q + m, compare1); 
	for (int i = 0; i < m; i++) { 
		
		
			cout << q[i].result << endl; 
	} 
} 

// Driver program 
int main() 
{ int n,q;
Fast;
cin >> n >> q;
	int a[n];
	for(int i = 0; i <n; i++)cin >> a[i];
	Query qr[q];int x, y;
	for(int i = 0; i < q; i++){
	    cin >> x >> y;
	    qr[i] = {x - 1, y - 1, i,0};
	}
	int m = sizeof(qr) / sizeof(qr[0]); 
	queryResults(a, n, qr, m); 
	printResults(qr, m); 
	return 0; 
} 


Measured memory_bytes: 17384