You are given an array of integers A of length n.
It is necessary to answer m queries of the form "report the number of different numbers of a subsegment of array A from the element with index l to the element with index r" (both boundaries of the subsegment are included, the array is numbered from one).
Input:
The first line contains two numbers: n - the number of array elements and m - the number of requests (1 <= n, m <= 10
5).
The second line contains n integers A
i - array elements (0 <= A
i <= 10
6).
Then there are m lines, each containing two numbers l and r - the boundaries of the subsegment for each query (1 <= l <= r <= n).
Output:
In a single line print m space-separated numbers - for each query, the number of different numbers on the corresponding subsegment.
Example:
| Input |
Output |
7 5
1 3 1 2 2 4 1
1 3
4 5
37
24
77 |
2 1 3 3 1 |