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;
typedef long long ll;

template <typename T>
struct FenwickTree {
	int n; // [1, n]
	vector<T> bit;
	FenwickTree(int n) : n(n), bit(n+1) {}
	T sum(int i) {
		T s = 0;
		while (i > 0) {
			s += bit[i];
			i -= i&-i;
		}
		return s;
	}
	void add(int i, T x) {
		while (i <= n) {
			bit[i] += x;
			i += i&-i;
		}
	}
};

int main() {
	int N, Q;
	cin >> N >> Q;
	vector<int> C(N);
	for (auto& x : C) cin >> x;
	vector<pair<int,int>> LR;
	map<int,map<int,int>> ans;
	for (int i = 0; i < Q; ++ i) {
		int x, y;
		cin >> x >> y;
		LR.push_back({x,y});
		ans[y][x] = 0;
	}
	vector<int> hoge(N+1, -1);
	FenwickTree<int> bit(N);
	for (int p = 1; p <= N; ++ p) {
		int prev = hoge[C[p-1]];
		if (prev != -1) {
			bit.add(prev, -1);
		}
		hoge[C[p-1]] = p;
		bit.add(p, 1);
		if (ans.count(p)) {
			for (auto& x : ans[p]) {
				int q = x.first;
				x.second = bit.sum(p) - bit.sum(q-1);
			}
		}
	}
	for (auto x : LR) {
		cout << ans[x.second][x.first] << endl;
	}
}
