Bancadas vizinhas

Time limit: 3000 msMemory limit: 256 MB

Há $n$ bancadas, numeradas de $1$ a $n$ , e a bancada $i$ tem capacidade $a_i$ . Elas serão colocadas em uma roda. A capacidade de uma ligação entre duas bancadas vizinhas é a soma de suas capacidades.

A qualidade da roda é a menor capacidade entre suas ligações, incluindo a ligação entre a última e a primeira bancada. Construa uma ordem que maximize essa qualidade. Bancadas com capacidades iguais continuam sendo objetos distintos.

Input

A primeira linha contém $n$ ( $3\le n\le200\,000$ ). A segunda contém $a_1,\ldots,a_n$ ().

Output

Imprima a maior qualidade possível na primeira linha. Na segunda, imprima uma permutação dos índices de $1$ a $n$ que atinja essa qualidade. Qualquer ordem ótima será aceita.

Samples

Sample 1

Input

4
1 2 3 4

Output

4
1 3 2 4

As somas vizinhas são 4, 5, 6 e 5. Não é possível obter qualidade maior que 4.

Sample 2

Input

3
5 5 5

Output

10
1 2 3

Toda ordem tem qualidade 10.