Мальчик Антон решает вступительную работу в летний математический лагерь. В ней N заданий, которые можно выполнять в произвольном порядке. Разные задачи требуют разного времени для решения. При этом известно, что если задание с номером i выполнять j-м по счету, Антону потребуется T
i*j
времени: чем больше думаешь, тем больше устаешь. Например, если начать с первой задачи, а затем выполнить вторую, то потребуется T
1*1 + T
2*2 времени, а если выполнить сначала вторую задачу, а затем первую – то T
2*1 + T
1*2. Подскажите Антону, в каком порядке нужно решать задачи, чтобы на выполнение всей работы ушло как можно меньше времени.
Входные данные
В первой строке вводится число N, во второй строке —N чисел через пробел T
1, T
1, …, T
N, разделенные пробелами. Все числа целые и удовлетворяют следующим ограничениям: 0 < N ≤ 10, 0 < T
i ≤ 100.
Выходные данные
Требуется вывести сначала минимальное время, за которое можно решить все задачи, а затем – номера задач в том порядке, в котором их нужно решать, чтобы уложиться в это время. Все числа разделяются пробелами. Если решений несколько, нужно выдать любое из них.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
1
23 |
23
1 |
| 2 |
2
52 37 |
126
1 2 |