P10073 [GDKOI2024 Junior] Farming Jungle II

Zayin is a wizard who fights monsters. This time, he will face $n$ monsters standing in a line, where the health of the $i$-th monster is $a_i$. Zayin knows many forbidden spells. In this battle, he decides to use a spell called "Lightning Combo" to defeat all monsters at once. Let us see how this spell works. - First, Zayin chooses a monster $i(1 \leq i \leq n)$ and an initial spell power $x$. - Then the spell first hits monster $i$. After that, for every step except the first target, Zayin may choose a monster that has not been hit by this spell, and is adjacent to at least one monster that has already been hit. - The first monster hit takes $x$ damage, the second target takes $x-1$ damage, the third takes $x-2$ damage, and so on. It is not hard to see that each monster will be hit exactly once. If the damage a monster takes is not less than its health, it is considered dead. Zayin wants to show his skill as an advanced wizard, so under the condition that he can kill all monsters using only one spell, he wants to use the smallest possible initial power $x$. You need to find the minimum required initial power and provide a valid plan. If there are multiple different plans, you may output any one of them.

The first line contains two integers $d, n$, representing the test point id and the number of monsters. The next line contains $n$ integers, where the $i$-th integer $a_i$ denotes the health of the $i$-th monster.

The first line outputs an integer $x$, the minimum initial power. The second line outputs $n$ indices separated by spaces, $monster_i(1 \leq i \leq n)$, where $monster_i$ denotes the monster hit at the $i$-th strike.

For all testdata, it is guaranteed that $1 \leq n \leq 5 \times 10^6$, and $1 \leq a_i \leq 10^9$. | Test Point ID | $n\leq$ | | :----------: | :----------: | | $1$ | $10$ | | $2$ | $20$ | | $3$ | $500$ | | $4$ | $5000$ | | $5$ | $5\times 10^4$ | | $6,7$ | $5\times 10^5$ | | $8,9,10$ | $5\times 10^6$ | Translated by ChatGPT 5