Вася недавно начал тренироваться стрельбе из пистолета. Сегодня тренер предложил ему следующее задание. Он выставил на стол \(n\) банок в ряд. Банки пронумерованы слева направо от \(1\) до \(n\). Чтобы выполнить задание, Васе предстоит сбить каждую из банок ровно по одному разу. При этом порядок, в котором Вася будет сбивать банки, он выбирает самостоятельно.
Вася знает, что прочность \(i\)-й банки равна \(a_i\). Это значит, что если Вася уже сбил \(x\) банок и сейчас начнет стрелять в \(i\)-ю банку, то, чтобы сбить эту банку, ему понадобится \((a_i \cdot x + 1)\) выстрел. Считайте, что если Вася начал стрелять в банку номер \(i\), то он будет стрелять в нее, пока он ее не собьет.
Определите такой порядок стрельбы по банкам, что Вася сделает минимально возможное количество выстрелов, чтобы сбить каждую из \(n\) банок ровно по одному разу.
Выходные данные
В первую строку выведите минимальное количество выстрелов, которые должен сделать Вася, чтобы сбить каждую из \(n\) банок ровно по одному разу.
Во вторую строку выведите последовательность из \(n\) различных целых чисел от \(1\) до \(n\) — номера банок в том порядке, в котором Вася должен по ним стрелять, чтобы минимизировать количество выстрелов. Если подходящих последовательностей несколько, разрешается вывести любую из них.
Примечание
В первом примере Вася может сначала стрелять в первую банку. Он собьет ее с первого выстрела, так как до этого не сбивал ни одну банку. После этого он должен стрелять в третью банку. Чтобы сбить ее, он потратит \(20 \cdot 1 + 1 = 21\) выстрел. После этого останется только вторая банка. Чтобы сбить ее, Вася сделает \(10 \cdot 2 + 1 = 21\) выстрел. Таким образом, суммарно Вася сделает \(1 + 21 + 21 = 43\) выстрела.
Во втором примере не важно, в какой последовательности стрелять по банкам, так как они все имеют одинаковую прочность.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
20 10 20
|
43
1 3 2
|
|
2
|
4
10 10 10 10
|
64
2 1 4 3
|
|
3
|
6
5 4 5 4 4 5
|
69
6 1 3 5 2 4
|
|
4
|
2
1 4
|
3
2 1
|