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>
using namespace std;
const int maxn = 5e5+5;
int n,q,pre[maxn],clr[maxn],ans[maxn];
int lsb(int x){
	return (x&(-x));
}	
int bit[maxn];
void add(int x,int z){
	while (x<=n){bit[x]+=z;x+=lsb(x);}	
}
int query(int x){
	int ans = 0;
	while (x){
		ans += bit[x];
		x -= lsb(x);
	}
	return ans;
}
struct quest{
	int id,l,r;
	bool operator < (const quest &b) const {
		return r < b.r;	
	}
} qs[maxn];

int main(){
	cin >> n >> q;
	for (int i=1;i<=n;i++){
		scanf("%d",&clr[i]);
		pre[i]=ans[clr[i]];		
		ans[clr[i]]=i;
	}
	for (int i=1,l,r;i<=q;i++){
		scanf("%d%d",&l,&r);
		qs[i]=(quest){i,l,r};	
	}
	sort(qs+1,qs+q+1);
	int bd=0;
	for (int i=1;i<=q;i++){
		while (qs[i].r > bd) add(pre[++bd]+1,1);
		ans[qs[i].id]=query(qs[i].l)-qs[i].l+1;
	}
	for (int i=1;i<=q;i++){
		printf("%d\n",ans[i]);	
	}
	return 0;
}