У Алисы есть целочисленная последовательность \(a\) длины \(n\) и все ее элементы различны. Она выбирает из \(a\) подпоследовательность длины \(m\) и определяет ценность подпоследовательности \(a_{b_1},a_{b_2},\ldots,a_{b_m}\) как \(\)\sum_{i = 1}^m (m \cdot a_{b_i}) - \sum_{i = 1}^m \sum_{j = 1}^m f(\min(b_i, b_j), \max(b_i, b_j)),\(\) где \(f(i, j)\) обозначает \(\min(a_i, a_{i + 1}, \ldots, a_j)\).
Алиса хочет, чтобы вы помогли ей максимизировать ценность выбираемой подпоследовательности.
Последовательность \(s\) является подпоследовательностью \(t\), если \(s\) может быть получена из \(t\) удалением нескольких (возможно, ни одного или всех) элементов.
Выходные данные
Выведите максимальное значение, которое может получить Алиса.
Примечание
В первом примере Алиса может выбрать подпоследовательность \([15, 2, 18, 13]\), которая имеет ценность \(4 \cdot (15 + 2 + 18 + 13) - (15 + 2 + 2 + 2) - (2 + 2 + 2 + 2) - (2 + 2 + 18 + 12) - (2 + 2 + 12 + 13) = 100\).
Во втором примере существует множество подпоследовательностей ценности \(176\), одна из них — \([9, 7, 12, 20, 18]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 4
15 2 18 12 13 4
|
100
|
|
2
|
11 5
9 3 7 1 8 12 10 20 15 18 5
|
176
|
|
3
|
1 1
114514
|
0
|
|
4
|
2 1
666 888
|
0
|