Description

After days of practice in the computer lab, LYD learned the art of separation and fusion from the esteemed Divine Cow Du. Before leaving, Divine Cow Du gave him a test...

Divine Cow Du created $n$ regions, arranged closely in a row and numbered from $1$ to $n$. In each region lies a golden key of the OI world, each with a certain value. Naturally, LYD wants to obtain all of them. However, Divine Cow Du stipulated that LYD cannot take all the keys at once but must take them one by one. To quickly gather all the golden keys, LYD employs the newly learned skills of separation and fusion.

Initially, LYD can choose any region between $1$ and $n-1$ to enter, which we denote as $k$. Upon entering, LYD will undergo separation in region $k$, splitting into two smaller LYD entities. At the moment of separation, a wall rises between regions $k$ and $k+1$, dividing the original range into two independent intervals: $1..k$ and $k+1..n$. Each smaller LYD can then choose any region except the end of their respective interval (i.e., from $1..k-1$ or $k+1..n-1$) to undergo further separation, resulting in four even smaller LYD entities... This process repeats until each tiny LYD finds itself in an interval consisting of only one region, at which point it can pick up the coveted golden OI key.

However, LYD cannot exist indefinitely as multiple separate entities in the world. These smaller LYD entities will eventually merge back together. When merging, the wall between their intervals disappears, and the value gained from the fusion is calculated as $(\text{sum of the golden key values at the left and right ends of the merged interval}) \times (\text{value of the golden key in the region where the separation originally occurred})$.

For example, if LYD separated in region $2$ of the interval $1..3$, splitting into intervals $1..2$ and $3..3$, the value gained upon merging would be $(\text{value of key 1} + \text{value of key 3}) \times (\text{value of key 2})$.

LYD asks you to write a program to determine the maximum total value obtainable and to output the sequence of regions where separation occurs, ordered from the earliest separation stage to the latest and from left to right within each stage. If there are multiple possible solutions, choose the one where the separation regions are as far left as possible (i.e., the lexicographically smallest sequence).

For example, first print the region where the initial split occurs, then print the regions for the subsequent splits from left to right, and so on.

Input Format

The first line contains a positive integer $n$. The second line contains $n$ positive integers $a_i$, separated by spaces, representing the values of the golden keys in regions $1$ to $n$.

Output Format

The first line should contain a single number, representing the maximum value obtainable.

The second line should list the regions where separation occurs, ordered from the earliest stage to the latest and from left to right within each stage. If there are multiple solutions, choose the one with the lexicographically smallest sequence.

Sample 1

7
1 2 3 4 5 6 7

238
1 2 3 4 5 6

Constraints and Hints

For $20\%$ of the data, $n\le 10$;
For $40\%$ of the data, $n\le 50$;
For $100\%$ of the data, $n, a_i\le 300$, ensuring that all intermediate and final results fit within a 32-bit unsigned integer.