D-query - MarisaOJ: Marisa Online Judge

You are given array

$A$ of

$n$ integers. There are

$q$ queries, each of the form

$(l, r)$ , count the number of distinct values in the subarray

$A_l,A_{l + 1},...,A_r$ . ### Input - The first line contains 2 integers

$n, q$ . - The second line contains

$n$ integers

$A_i$ . - The next

$q$ lines, each line contains 2 integers

$l_i, r_i$ , a query. ### Output - Print

$q$ integers, the answers to

$q$ queries. ### Constraints -

$1 \le n, q\le 10^5$ . -

$1 \le A_i \le 10^5$ . ### Example Input:

$5 3 1 2 2 3 2 1 3 1 5 3 4$

Output:

$2 3 2$

Topic

Data structure

Rating

1600

Solution (0)

Solution