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;
#define rep(i, a, b) for(register int i = a; i <= b; i++)
#define per(i, a, b) for(register int i = a; i >= b; i--)
typedef long long LL;
const LL mod = 1e9 + 7;
const int N = 5e5 + 5;

int n, Q, ans[N], c[N], nex[N], cur[N], t[N];
struct Que {
	int l, r, id;
} q[N];

void update(int x, int k) {
	if(!x) return; 
	while(x <= n) {
		t[x] += k;
		x += x&-x;
	}
}

int Query(int x) {
	int res = 0;
	while(x) {
		res += t[x];
		x -= x&-x;
	}
	return res;
}

bool cmp(Que a, Que b) {
	return a.r < b.r;
}

int main() {
	cin>>n>>Q;
	rep(i, 1, n) {
		scanf("%d", &c[i]);
		nex[i] = cur[c[i]];
		cur[c[i]] = i;
	}
	rep(i, 1, Q) {
		scanf("%d%d", &q[i].l, &q[i].r);
		q[i].id = i;
	}
	sort(q + 1, q + Q + 1, cmp);
	int now = 0;
	rep(i, 1, Q) {
		while(now < q[i].r) {
			now++;
			update(nex[now], -1);
			update(now, 1);
		}
		ans[q[i].id] = Query(q[i].r) - Query(q[i].l - 1);
	} 
	rep(i, 1, Q)
	    cout<<ans[i]<<endl;
	return 0;
}