У Алисы есть целочисленная последовательность $$$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$$$ удалением нескольких (возможно, ни одного или всех) элементов.