Max Sum of Strengths after At-Most-One Adjacent Swap (per index)

You are given an array of positive integers. You may choose several pairwise non-adjacent index pairs (i,i+1) and swap their elements, or make no swaps at all. Each element takes part in at most one swap. Indices start at 0, and after the swaps the strength of the array is Σ arr[i]×(i+1). Find the maximum strength.

This site added a standard input/output protocol.

输入格式

The first line contains n (1 ≤ n ≤ 100000), and the second line contains n integers arr[i] (1 ≤ arr[i] ≤ 100000).

输出格式

Output the maximum achievable strength sum.

样例 1

输入：

5
1 9 7 3 2

输出：

66

样例 2

输入：

3
3 2 1

输出：

11

样例 3

输入：

1
1

输出：

1