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 <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 500050
#define M 200020
int mx = 0, n, m, b[N], ans[N], tree[N << 1], last[N], h[N << 1];
struct node { int x, y, num; }a[M];
bool cmp(node x, node y) { return x.y < y.y || (x.y == y.y && x.x < y.x); }
void insert(int x, int y) { for (; x <= n; x += x & -x) tree[x] += y; }
int query(int x) {
    int y = 0; for (; x; x -= x & -x) y += tree[x];
    return y;
}
int main() {
    scanf("%d", &n); scanf("%d", &m);
    for (int i = 1; i <= n; i++) scanf("%d", &b[i]), last[i] = h[b[i]], h[b[i]] = i, mx = max(mx, b[i]);
    int q = sqrt(n);
    for (int i = 1; i <= m; i++) scanf("%d%d", &a[i].x, &a[i].y), a[i].num = i;
    sort(a + 1, a + m + 1, cmp); int tmp = 0;
    for (int i = 1; i <= m; i++) {
        while (tmp < a[i].y) {
            tmp++; if (last[tmp]) insert(last[tmp], -1);
            insert(tmp, 1);
        }ans[a[i].num] = query(tmp) - query(a[i].x - 1);
    }for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
    return 0;
}