to (inclusive) are set in a pool of lava. As can be expected, the stones are very hot. In fact, they can be hotter than the surface of the sun! must jump from the start () to the other side (), but he can only jump at most stones forward at a time. Fortunately, has a pair of cooling boots that can cool any stone to 0 degrees. However, the boots require one unit of power per degree cooled, and power is very expensive! Can you help find the minimum units of power required to jump to the other side of the lava pool?developed a new hopscotch. In this game, a row of stones conveniently numbered
can only walk on stones that are 0 degrees.
() from stone .can only hop forwards to stone
Since , he can hop to () on his first hop.starts from
The first line will contain and , separated by a space.
The second line will contain all () separated by spaces.
There is a trailing newline(ASCII code 10) at the end of input.
Output the minimum power cost to hop from 0 to () on the first line.
Output the indices of the stonesmust hop on to use the minimum amount of power on the second line, separated by spaces and in ascending order.
If there are multiple ways to achieve the minimum power, output the lexicographically most sequence of the indices.
For all subtasks:
It is guaranteed the power required on any valid path will not exceed
Subtask 0 [1p]
Subtask 1 [1p]
Subtask 2 [3p]
Subtask 3 [10p]
No additional constriants
Batches correspond to the respective subtasks.
The non-batched test cases are the sample cases.
Sample Input 1
16 4 4 5 3 12 2 6 3 6 5 5 16 1 10 9 13 12
Sample Output 1
20 3 5 9 12 14
Sample Input 2
16 2 4 13 6 6 4 1 7 1 0 15 3 0 8 11 5 8
Sample Output 2
32 1 3 5 6 8 9 11 12 13 15