Maximum Final Weight Sum

You are given n numbers. The i-th number has an original weight \(w_i\). You must choose these numbers one by one in some order. When you make the \(i\)-th selection and choose a number whose original weight is \(k\), then each of the remaining (not yet selected) numbers has its weight increased by

[ (-1)^{i+k+1} \times k. ]

The final weight of a number is its weight at the moment it is selected. Your task is to find a selection order (a permutation of the \(n\) numbers) that maximizes the sum of the final weights of all the numbers. In other words, if the numbers are chosen in order \(k_1,k_2,\dots,k_n\), then the final sum is

[ \sum_{i=1}^n \left(w_{\pi(i)} + \sum_{p=1}^{i-1} (-1)^{p+k_{\pi(p)}+1} \times k_{\pi(p)}\right) = \sum_{i=1}^n w_i + \sum_{p=1}^{n-1} (n-p) \cdot (-1)^{p+k_{\pi(p)}+1} \times k_{\pi(p)}. ]

Output the maximum achievable final sum.

inputFormat

The first line contains a single integer \(n\) (the number of numbers). The second line contains \(n\) space-separated integers: \(w_1, w_2, \dots, w_n\), representing the original weights of the numbers.

outputFormat

Output a single integer: the maximum possible sum of the final weights when following an optimal selection order.

sample

1
5

5