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
// Mo's algorithm

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

int main(){
	int n,q; scanf("%d%d",&n,&q);
	vector<int> a(n);
	rep(i,n) scanf("%d",&a[i]), a[i]--;

	vector<int> l(q),r(q);
	rep(i,q) scanf("%d%d",&l[i],&r[i]), l[i]--;

	int m=sqrt(n);
	vector<int> p(q);
	iota(p.begin(),p.end(),0);
	sort(p.begin(),p.end(),[&](int i,int j){
		return make_pair(l[i]/m,r[i])<make_pair(l[j]/m,r[j]);
	});

	int cnt=0;
	vector<int> freq(n);
	auto add=[&](int x){
		if(freq[a[x]]==0) cnt++;
		freq[a[x]]++;
	};
	auto del=[&](int x){
		freq[a[x]]--;
		if(freq[a[x]]==0) cnt--;
	};

	vector<int> ans(q);
	int xl=0,xr=0;
	for(int i:p){
		while(xl<l[i]) del(xl++);
		while(xl>l[i]) add(--xl);
		while(xr<r[i]) add(xr++);
		while(xr>r[i]) del(--xr);
		ans[i]=cnt;
	}
	rep(i,q) printf("%d\n",ans[i]);

	return 0;
}
