Вам дан массив \(a\) из \(n\) целых чисел. Вы можете совершить следующую операцию любое число раз (0 или больше раз):
- Выбрать \(2\) индекса \(i\),\(j\) где \(1 \le i < j \le n\) и заменить \(a_k\) для всех \(i \leq k \leq j\) значением \(|a_i - a_j|\)
Выведите максимальную сумму всех элементов конечного массива, которую вы можете получить таким образом.
Выходные данные
Для каждого набора входных данных выведите сумму конечного массива.
Примечание
В первом примере невозможно достичь сумму \(> 3\) используя операцию, таким образом ответ \(3\).
Во втором примере можно показать, что максимальная достижимая сумма равна \(16\). Используем операцию \((1,2)\) и преврати массив из \([9,1]\) в \([8,8]\), таким образом ответ равен \(16\).
В третьем примере можно показать, что невозможно достичь суммы \(> 18\) используя операцию, таким образом ответ \(18\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
1 1 1
2
9 1
3
4 9 5
|
3
16
18
|