Lightning Combo

Zayin is a wizard fighting a line of n monsters, where the i-th monster has health \(a_i\). In order to defeat them all in one go, he uses a spell called "Lightning Combo." The spell works as follows:

1. Zayin selects a starting monster with index \(i\) (\(1 \le i \le n\)) and an initial power \(x\).
2. The spell first hits monster \(i\), dealing \(x\) damage.
3. Then, repeatedly, Zayin can choose an unhit monster that is adjacent to at least one monster already hit. The second hit deals \(x-1\) damage, the third deals \(x-2\) damage, and so on. Each monster is hit exactly once.

A monster dies if the damage it receives is at least its health. In other words, if a monster is hit in the \(k\text{-th}\) turn it receives a damage of \(x-(k-1)\) and it dies if \(x-(k-1)\ge a_j\).

Zayin wishes to kill all monsters with a single spell usage while minimizing the initial power \(x\). Your task is to compute the minimum \(x\) required and provide a valid attack order (i.e. a scheme) in which the spell is cast. Note that if the starting index is \(i\) then one valid strategy is to choose the monsters in an order that respects connectivity. For example, one may choose to first extend to the left consecutively and then to the right (or vice versa). However, the damage each monster receives will depend on its order in the sequence. In a valid scheme:

• If the spell is cast in the order p₁, p₂, ..., p_n (with \(p_1=i\)), then monster p_j receives damage \(x-(j-1)\).
• Since a monster at position \(j\) (relative to the starting index \(i\)) must be hit no earlier than its distance \(|j-i|\), it is necessary that \(x - (j-1) \ge a_{p_j}\) for all \(j\), and in particular \(x\ge a_{p_j} + (j-1)\).

Your goal is to choose an index \(i\) and an ordering of all monsters (which respects the rule of selecting an unhit monster adjacent to a hit monster) so that the minimal \(x = \min_{\text{valid orders}}\max_{1\le j\le n}\bigl(a_{p_j}+(j-1)\bigr)\) is achieved. If there are multiple schemes achieving the minimum \(x\), you may output any one of them.

Input Format: The first line contains an integer \(n\) denoting the number of monsters. The second line contains \(n\) integers \(a_1,a_2,\ldots,a_n\) representing the health values of the monsters.

Output Format: The output should contain two lines. The first line contains the minimum initial power \(x\). The second line contains a permutation of \(1, 2, \ldots, n\) representing a valid attack order. In this order, the first number is the index of the monster chosen as the starting point and subsequent numbers follow the order in which the monsters are hit.

inputFormat

The first line of input is an integer \(n\) (the number of monsters). The second line contains \(n\) space-separated integers \(a_1, a_2, \ldots, a_n\), where \(a_i\) denotes the health of the \(i\text{-th}\) monster.

outputFormat

Output two lines:

• The first line is an integer representing the minimum initial power \(x\) needed.
• The second line is a permutation of \(1, 2, \ldots, n\) representing a valid attack order that achieves the kill.

sample

3
3 1 2

4
2 1 3