No mex m#11792
You are given an array of integers and two integers and .
For each m = l, l+1, \dots, r, solve the following problem:
Find the minimum number of elements in the array that need to be changed (replaced with any non-negative integers) so that there does not exist a nonempty subarray whose mex is equal to .
The mex (minimum excluded value) of a set of non-negative integers is the smallest non-negative integer that is not present in the set. The mex of \{1,0,2,4\} is . The mex of \{1,2,3\} is . The mex of \{0,2,3\} is .
The first line contains three integers n, l, r (0 \le l \le r \le n \le 5 \cdot 10^5, n \ge 1).
The second line contains integers a_1, a_2, \ldots, a_n (0 \le a_i \le n).
In a single line, output r - l + 1 integers, where the -th integer represents the minimum number of elements that need to be changed for m = l + i - 1.
Example 1
Example 2
Example 3
In the first sample, we can change all non elements to . By doing that, consuming 3 operations, we achieve that mex will be bigger than on each subarray. Changing all elements to , using 2 operations, will make mex equal to on each subarray. It can be shown that this is the best possible answer for the m=0 and m=1.
( points): n=l=r;
( points): l=r;
( points): n \le 1000;
( points): a_i = i \mod c for some c \ge 1;
( points): n \le 2 \cdot 10^5;
( points): no additional constraints;