We have N colored balls arranged in a row from left to right; the color of the i-th ball from the left is c_i.

You are given Q queries. The i-th query is as follows: how many different colors do the l_i-th through r_i-th balls from the left have?

Constraints

* 1\leq N,Q \leq 5 \times 10^5
* 1\leq c_i \leq N
* 1\leq l_i \leq r_i \leq N
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N Q
c_1 c_2 \cdots c_N
l_1 r_1
l_2 r_2
:
l_Q r_Q


Output

Print Q lines. The i-th line should contain the response to the i-th query.

Examples

Input

4 3
1 2 1 3
1 3
2 4
3 3


Output

2
3
1


Input

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


Output

1
2
2
1
2
2
6
3
3
3
#include<bits/stdc++.h>
#define ld long double
#define ll long long
#define st first
#define nd second
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define pb push_back
using namespace std;

const int base = (1<<20);
int tree[2*base+1];
void add(int l, int r) {
	l += base;
	r += base;
	tree[l]++;
	if(l != r) tree[r]++;
	while(l/2 != r/2) {
		if(l%2==0) tree[l+1]++;
		if(r%2==1) tree[r-1]++;
		l/=2;
		r/=2;
	}
}
int query(int x) {
	int res = 0;
	x += base;
	while(x) {
		res += tree[x];
		x/=2;
	}
	return res;
}
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n, q;
	cin>>n>>q;
	vector<int> c(n);
	vector<vector<pii>> queries(n+1);
	for(int i=0; i<n; ++i) {
		cin>>c[i];
	}
	for(int i=0; i<q; ++i) {
		int l, r;
		cin>>l>>r;
		queries[r-1].push_back({l-1, i});
	}
	vector<int> res(q);
	vector<int> last(n+1, -1);
	for(int i=0; i<n; ++i) {
		add(last[c[i]]+1, i);
		for(auto j: queries[i]) {
			res[j.nd] = query(j.st);
		}
		last[c[i]]=i;
	}
	for(int i=0; i<q; ++i) {
		cout<<res[i]<<'\n';
	}
}
