Maximizing Treat Sales Profit

John has purchased \(N\) (\(1 \leq N \leq 2000\)) tasty treats for his cows. The treats are arranged in a row and numbered from \(1\) to \(N\). Each treat \(i\) has an initial value \(V_i\) (\(1 \leq V_i \leq 1000\)). John sells one treat per day and can remove a treat from either end of the row. When a treat is sold on day \(a\), its sale price is \(V_i \times a\). The goal is to determine the maximum profit John can obtain by selling all the treats in an optimal order.

Since the treats improve with age, selling them later yields a higher multiplier. However, because John can only remove a treat from either end of the sequence, he must choose the order strategically to maximize his revenue.

inputFormat

The first line contains an integer \(N\), representing the number of treats. The second line contains \(N\) space-separated integers \(V_1, V_2, \ldots, V_N\) indicating the initial values of the treats in order.

outputFormat

Output a single integer: the maximum profit achievable by selling all the treats optimally.

sample

3
1 3 1

12