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;
using ivec = vector<int>;

int main() {
	int n, p, q;
	ios::sync_with_stdio(false), cin.tie(nullptr);
	for (cin >> n >> q, p = 1; p*p <= n; ++p);
	ivec c(n);
	for (auto &color: c)
		cin >> color, --color;
	ivec l(q), r(q); priority_queue<tuple<int,int,int>> s;
	for (int m = p-1, i = 0; i < q; ++i)
		cin >> l[i] >> r[i], s.emplace(--r[i]/m,--l[i]/m,i);
	const auto s_dec = [](int &count, int &size) { if (--count == 0) --size; };
	const auto s_inc = [](int &count, int &size) { if (++count == 1) ++size; };
	ivec count(n,0), ans(q); ++count[c[0]];
	for (int g = 0, h = 0, size = 1; not s.empty(); s.pop()) {
		int i = get<2>(s.top()), u = l[i], v = r[i]; 
		while (h > v)
			s_dec(count[c[h--]],size);
		while (h < v)
			s_inc(count[c[++h]],size);
		while (g < u)
			s_dec(count[c[g++]],size);
		while (g > u)
			s_inc(count[c[--g]],size);
		ans[i] = size; }
	for (auto a: ans)
		cout << a << '\n'; }
