Zayin is a wizard who fights monsters. This time, he is facing $n$ monsters standing in a row, where the $i$-th monster has $a_i$ health points.

Zayin knows many suppressed spells. In this battle, he decides to use a spell called "Lightning Combo" to defeat all the monsters at once. Let's see how this spell works:

• First, Zayin chooses a monster $i$ ($1 \le i \le n$) and an initial spell power $x$.
• Then, the spell first hits monster $i$. Subsequently, for all targets other than the first one, Zayin can choose a monster that has not been hit by the spell yet and is adjacent to one of the monsters that has already been hit.
• The first target monster hit receives $x$ damage, the second target monster receives $x-1$ damage, the third receives $x-2$ damage, and so on. It is easy to see that each monster will be hit exactly once.

If a monster receives damage no less than its health points, it is considered dead.

Zayin wants to demonstrate his ability as a high-level wizard, so he hopes to use the minimum initial power $x$ such that he can kill all monsters using the spell exactly once.

You need to find the minimum initial power required and provide a valid sequence. If there are multiple different solutions, any one of them is acceptable.

Input

The first line contains two integers $d$ and $n$, representing the test case number and the number of monsters.

The next line contains $n$ integers, where the $i$-th integer $a_i$ represents the health of the $i$-th monster.

Output

The first line outputs an integer $x$, representing the minimum initial power.

The second line outputs $n$ space-separated indices $monster_i$ ($1 \le i \le n$), where $monster_i$ represents the $i$-th target monster hit.

Constraints

For all test data, it is guaranteed that $1 \le n \le 5 \times 10^6$ and $1 \le a_i \le 10^9$.

Examples

Input 1

1 10
19 9 12 5 10 7 16 15 17 12

Output 1

25
1 2 3 4 5 6 7 8 9 10