Андрей только начинает придумывать задачи, и это ему тяжело даётся. Поэтому он придумал странную задачу про перестановки\(^{\dagger}\), и просит её решить. Получится ли у вас это сделать?
Назовем стоимостью перестановки \(p\) длины \(n\) значение выражения:
\((\sum_{i = 1}^{n} p_i \cdot i) - (\max_{j = 1}^{n} p_j \cdot j)\). Найдите максимальную стоимость среди всех перестановок длины \(n\).
\(^{\dagger}\)Перестановкой длины \(n\) является массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) — перестановка, но \([1,2,2]\) не перестановка (\(2\) встречается в массиве дважды) и \([1,3,4]\) тоже не перестановка (\(n=3\), но в массиве встречается \(4\)).
Примечание
В первом наборе входных данных перестановкой с максимальной стоимостью является \([2, 1]\). Стоимость равна \(2 \cdot 1 + 1 \cdot 2 - \max (2 \cdot 1, 1 \cdot 2)= 2 + 2 - 2 = 2\).
Во втором наборе входных данных перестановкой с максимальной стоимостью является \([1, 2, 4, 3]\). Стоимость равна \(1 \cdot 1 + 2 \cdot 2 + 4 \cdot 3 + 3 \cdot 4 - 4 \cdot 3 = 17\).