Background

Updated on 2024/5/12: Two new sets of hack testdata were added, located at #31 and #32 of Subtask #5.

Updated on 2024/5/13: Due to excessive controversy, the difficulty has now been lowered to green. No further changes to the difficulty are considered for now.

Problem Description

In this contest, to help contestants complete the check-in problem smoothly, there are $n$ check-in locations. You and all of them are on the same straight road. We may regard this straight road as a number line. You are currently at the origin of the number line (i.e., coordinate $0$). The $i$-th check-in location is at coordinate $x_i$. In each unit of time, you can move at most $1$ unit of distance.

You need to check in at as many check-in locations as possible, and then return to the origin within $m$ units of time. The time for checking in can be ignored, and you may instantly complete check-ins for multiple different check-in locations that are at the same position.

To make it easier and smoother for contestants to check in, the problem setter also placed a check-in gift at the $p$-th check-in location. If a contestant has checked in here, then the time limit for returning to the origin can be delayed to $m+5$ units of time. Note: You may obtain the gift after time $m$, but you must return to the origin before $m+5$ units of time.

Find the maximum number of different check-in locations a contestant can check in at, and under this condition, minimize the lexicographical order of the set of indices of the checked-in locations (if there are multiple solutions, output any one solution).

Note: The lexicographical order of a set is equivalent to the lexicographical order of the sequence obtained by sorting the elements in the set in increasing order.

Input Format

The first line contains three integers $n,m,p$.

The second line contains $n$ integers in total. The $i$-th integer denotes $x_i$.

Output Format

The first line contains one integer $ans$, indicating the maximum number of check-in locations you can visit.

The second line outputs $ans$ positive integers, indicating the indices of the check-in locations to check in at in order.

This problem uses Special Judge. If there are multiple solutions, output any one of them.

3 11 3
1 -3 4 

3
1 2 3

5 15 3
-5 -10 0 5 10 

3
2 1 3 

Hint

Explanation for Sample $\small\text{1}$

Obviously, you can check in at all check-in locations. Just output any action plan whose total time does not exceed $16$.

Explanation for Sample $\small\text{2}$

There are $3$ different ways to choose $3$ check-in locations: $1$ $2$ $3$, $1$ $3$ $4$, $3$ $4$ $5$. Clearly, the first choice is optimal. Any of the following four action plans are acceptable: $1$ $2$ $3$, $2$ $1$ $3$, $3$ $1$ $2$, $3$ $2$ $1$.

Constraints and Notes

This problem uses bundled tests.

This problem uses "Special Judge".

Please note the impact of heavy input/output on program efficiency.

It is guaranteed that the time limit for this problem is sufficiently long.

For $100\%$ of the data, $1\leq p\leq n\leq 10^6$, $0\leq m\leq 10^{18}$, $-10^{18}\leq x_i\leq 10^{18}$.

Translated by ChatGPT 5