Background

HMR's LIS I

HMR's LIS II

After you helped HMR take down two problems by the genius LSK from AKIOI, LSK was very unhappy and decided to make things difficult for you (not for HMR).

Problem Description

LSK gives a sequence of length $n$ again, and asks you to find its IBvl sequence.

An IBvl sequence must satisfy the following:

1. An IBvl sequence satisfies $\forall ~ i \in (1,len] , L < a_i - a_{i-1} < R$, where $len$ is the length of the IBvl sequence.

2. The relative order of elements in the IBvl sequence must follow their relative order in the original sequence.

3. Among all sequences that satisfy the conditions, its length is the maximum.

We treat elements at different positions as different elements. Any two IBvl sequences are considered different if they differ in any chosen element.

Now you need to output the length of the IBvl sequence of the original sequence, and output the positions (in the original sequence) of each element in the $k$-th smallest sequence in lexicographical order (where the key for ordering is the element's position in the original sequence).

Input Format

The first line contains four integers $n$, $k$, $L$, $R$.

The second line contains $n$ integers, representing the sequence given by the genius LSK.

Output Format

The first line outputs the length of the IBvl sequence.

The second line outputs the positions of each element of the IBvl sequence in the original sequence.

5 3 2 4
6 8 0 2 7

1
3

Hint

Sample Explanation

For the given data, there are $5$ IBvl sequences in total: $\{6\},\{8\},\{0\},\{2\},\{7\}$.

Their index sequences (positions in the original sequence) are $\{1\},\{2\},\{3\},\{4\},\{5\}$, respectively.

The length of the IBvl sequence is $1$.

You are required to output the index sequence that is the $3$-rd smallest in lexicographical order, so the output is $3$.

Constraints and Notes

For $20\%$ of the testdata, $n \le 18$.

For $50\%$ of the testdata, $n \le 1000 , | l | , | r | \leq 10^9 , r-l>1 , 0 \le a[i] \le 10^9$.

For another $10\%$ of the testdata, $l=0 , r=10^9+1 , k=1$.

For another $20\%$ of the testdata, $l=0 , r=10^9+1 , k \le 3$.

For $100\%$ of the testdata, $n \le 5*10^5 , | l | , | r | \le 10^9 , r-l>1 , k \le 10^{13} , 0 \le a[i] \le 10^9$.

For all testdata, it is guaranteed to be valid and that a solution exists.

For the first $50\%$ of the testdata, the time limit is $1\text{s}$. For the remaining $50\%$, the time limit is $2\text{s}$ (kind not too strict about constant factors).

Translated by ChatGPT 5