Maximizing MEX Interval Value

Consider a sequence of n non‐negative integers each less than m. For any contiguous subsequence (interval) of the sequence, its mex is defined as the smallest non‐negative integer that does not appear in the interval. The value of a sequence is defined as the number of intervals whose mex is at least k.

You are given an array of n numbers (each in the range [0, m-1]) and an integer interval [l, r]. Let f(k) be the maximum possible value achievable by any rearrangement of the given array, where the value is determined by counting all intervals with mex \(\ge k\). This maximum is taken over all possible permutations of the array.

It is guaranteed that if we denote a_i as the frequency of integer i (for \(0 \le i \le m-1\)), then there exists a positive integer \(X\) such that \(a_i \in \{X, X+1\}\) for every \(0 \le i \le m-1\>.

Explanation on f(k):

In any rearrangement, an interval will have \(\textrm{mex} \ge k\) if and only if it contains every integer from \(0\) to \(k-1\). To maximize the number of such intervals, one optimal strategy is to arrange all occurrences of the integers \(0,1,\dots,k-1\) contiguously forming a block. Suppose the total number of occurrences of integers \(0,1,\dots,k-1\) is \[ T = \sum_{i=0}^{k-1} a_i. \] Then, by placing this block in the sequence appropriately, the maximum number of intervals covering the entire block is given by \[ \max_{1 \le L \le n-T+1} \; L \times (n - (L + T - 1) + 1) = \max_{1 \le L \le n-T+1} L \cdot (n - T - L + 2). \] A simple analysis shows that the maximum is achieved when the block is as centered as possible. If we define \[ M = n - T + 2,\] then the maximum product is obtained as \[ \lfloor M/2 \rfloor \times \lceil M/2 \rceil.\] Thus, for each \(k\) in the interval [l, r], you are to compute \[ f(k) = \lfloor (n-T+2)/2 \rfloor \times \lceil (n-T+2)/2 \rceil, \quad \text{where } T = \sum_{i=0}^{k-1} a_i.\]

inputFormat

The first line contains four integers n, m, l, and r, where n is the number of elements in the sequence, m is the upper bound for the elements (elements are in the range [0, m-1]), and [l, r] defines the range of k values for which you must compute f(k).

The second line contains n space-separated non-negative integers, representing the sequence. It is guaranteed that for every integer i in [0, m-1], its frequency a_i satisfies \(a_i \in \{X, X+1\}\) for some positive integer \(X\).

outputFormat

Output r - l + 1 space-separated integers, where the i-th integer represents f(k) for k = l + i - 1.

sample

10 5 1 3
0 1 0 2 1 3 2 4 3 4

25 16 9