#include <bits/stdc++.h>
using namespace std;
long long dp[2020][2020];
int main() {
	int n; cin >> n;
	int a[n]; for (int &i : a) cin >> i;
	int p[n]; iota(p, p + n, 0);
	sort(p, p + n, [&] (int x, int y) {
		return a[x] > a[y];
	});
	for (int l = 0; l < n; l++) {
		for (int r = 0; l + r < n; r++) {
			int now = l + r;
			dp[l + 1][r] = max(dp[l + 1][r], dp[l][r] + 1LL * a[p[now]] * abs(p[now] - l));
			dp[l][r + 1] = max(dp[l][r + 1], dp[l][r] + 1LL * a[p[now]] * abs(p[now] - (n - 1 - r)));
		}
	}
	long long ans = 0;
	for (int i = 0; i <= n; i++) 
		ans = max(ans, dp[i][n - i]);
	cout << ans;
}
### Prompt

Create a solution in cpp for the following problem:

There are N children standing in a line from left to right. The activeness of the i-th child from the left is A_i.

You can rearrange these children just one time in any order you like.

When a child who originally occupies the x-th position from the left in the line moves to the y-th position from the left, that child earns A_x \times |x-y| happiness points.

Find the maximum total happiness points the children can earn.

Constraints

* 2 \leq N \leq 2000
* 1 \leq A_i \leq 10^9
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N
A_1 A_2 ... A_N


Output

Print the maximum total happiness points the children can earn.

Examples

Input

4
1 3 4 2


Output

20


Input

6
5 5 6 1 1 1


Output

58


Input

6
8 6 9 1 2 1


Output

85

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long dp[2020][2020];
int main() {
	int n; cin >> n;
	int a[n]; for (int &i : a) cin >> i;
	int p[n]; iota(p, p + n, 0);
	sort(p, p + n, [&] (int x, int y) {
		return a[x] > a[y];
	});
	for (int l = 0; l < n; l++) {
		for (int r = 0; l + r < n; r++) {
			int now = l + r;
			dp[l + 1][r] = max(dp[l + 1][r], dp[l][r] + 1LL * a[p[now]] * abs(p[now] - l));
			dp[l][r + 1] = max(dp[l][r + 1], dp[l][r] + 1LL * a[p[now]] * abs(p[now] - (n - 1 - r)));
		}
	}
	long long ans = 0;
	for (int i = 0; i <= n; i++) 
		ans = max(ans, dp[i][n - i]);
	cout << ans;
}
```