Вам дан массив целых чисел А длиной n.
Необходимо ответить на m запросов вида "сообщите количество различных чисел подотрезка массива А от элемента с индексом l до элемента с индексом r" (обе границы подотрезка включены, массив нумеруется с единицы).
Входные данные:
В первой строке дано два числа: n - количество элементов массива и m - количество запросов (1 <= n, m <= 10
5).
Во второй строке дано n целых чисел A
i - элементы массива (0 <= A
i <= 10
6).
Далее дано m строк, в каждой по два числа l и r - границы подотрезка для каждого запроса (1 <= l <= r <= n).
Выходные данные:
В единственной строке выведите через пробел m чисел - для каждого запроса количестве различных чисел на соответствующем подотрезке.
Пример:
| Входные данные |
Выходные данные |
7 5
1 3 1 2 2 4 1
1 3
4 5
3 7
2 4
7 7 |
2 1 3 3 1 |