Ecrade купил колоду карт, пронумерованных от \(1\) до \(n\). Пусть ценность перестановки \(a\) длины \(n\) равна \(\min\limits_{i = 1}^{n - k + 1}\ \sum\limits_{j = i}^{i + k - 1}a_j\). Ecrade хочет найти среди всех перестановок карт самую ценную. Однако это кажется немного сложным, поэтому, пожалуйста, помогите ему!
Выходные данные
Для каждого набора входных данных выведите в первой строке наибольшую возможную ценность. Затем выведите \(n\) целых чисел \(a_1,a_2,\dots,a_n\) (\(1 \le a_i \le n\), все \(a_i\) различны) — элементы перестановки, которая имеет наибольшую ценность.
Если таких перестановок несколько, выведите любую из них.
Примечание
В первом наборе входных данных \([1,4,5,3,2]\) имеет ценность \(13\). Можно показать, что при \(k = 4\) ни одна перестановка длиной \(5\) не имеет ценность больше \(13\).
Во втором наборе входных данных \([4,2,5,7,8,3,1,6]\) имеет ценность \(18\). Можно показать, что ни одна перестановка длины \(8\) не имеет ценность больше \(18\) при \(k = 4\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
5 4
8 4
|
13
1 4 5 3 2
18
4 2 5 7 8 3 1 6
|