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 N = 5e5 + 5;
int n, m, a[N];
struct info {
	int l, r, index;
} q[N];
inline bool cmp(info x, info y) { return x.r < y.r; }
int ans[N], pre[N];
namespace BIT
{
	int tree[N];
	inline int lowbit(int x) { return x & -x; }
	inline void modify(int x, int val) {
		for (; x <= N; x += lowbit(x)) tree[x] += val;
	} 
	inline int query(int x) {
		int ans = 0;
		for (; x; x -= lowbit(x)) ans += tree[x];
		return ans;
	}
	inline int query(int l, int r) {
		return query(r) - query(l - 1);
	}
}
using namespace BIT;
int main(){
	scanf ("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) scanf ("%d", &a[i]);
	
	for (int i = 1; i <= m; i++) {
		scanf ("%d%d", &q[i].l, &q[i].r);
		q[i].index = i;
	}
	sort(q + 1, q + m + 1, cmp);
	
	int j = 1;
	for (int i = 1; i <= m; i++)
	{
		while (j <= q[i].r) {
			if (pre[a[j]]) modify(pre[a[j]], -1);
			modify(j, 1);
			pre[a[j]] = j;
			j++;
		}
		ans[q[i].index] = query(q[i].l, q[i].r);
	}
	
	for (int i = 1; i <= m; i++) printf ("%d\n", ans[i]);
  return 0;
}