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;

struct bit {
    vector<long> t;
    bit(int n) : t(n + 1) {}
    void upd(int a, long n) {
        for(a++; a < t.size(); a += a & -a)
            t[a] += n;
    }
    long get(int a) const {
        long r = 0;
        for(; a; a &= a - 1)
            r += t[a];
        return r;
    }
};
int c[555555], d[555555], x[555555];
tuple<int, int, int> p[555555];
int main() {
    int n, q;
    cin >> n >> q;
    for(int i = 0; i < n; i++)
        cin >> c[i], c[i]--;
    for(int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        p[i] = {r, l - 1, i};
    }
    sort(p, p + q);
    fill(d, d + n, -1);
    bit b(n);
    int j = 0;
    for(int i = 0; i < n; i++) {
        if(d[c[i]] >= 0)
            b.upd(d[c[i]], -1);
        b.upd(d[c[i]] = i, 1);
        for(; j < q; j++) {
            auto [r, l, m] = p[j];
            if(r != i + 1)
                break;
            x[m] = b.get(r) - b.get(l);
        }
    }
    for(int i = 0; i < q; i++)
        cout << x[i] << '\n';
    return 0;
}
