Military Drill

There are n students in a class, numbered from 1 to n, standing in a single line in increasing order. The instructor makes the students stand in military drill formation. After standing for a long while, the instructor decides to let the students leave one by one to rest but in an orderly fashion.

The instructor starts from the left of student 1 and walks to the right of student n, and then turns back to student 1. As he passes by a student, he can call that student to leave immediately or wait until he meets that student again during his return journey. However, for each student i, there is an associated "bad value" \(w_i\) (which can be positive, zero, or negative), and the instructor wishes to maximize the weighted sum of the exit orders defined as:

[ \text{Score} = \sum_{i=1}^{n} r_i \times w_i, ]

where \(r_i\) is the exit order of the i-th student (with \(r_i = 1\) for the first student to leave, \(r_i = n\) for the last one). To reward higher bad values (i.e. such students get to rest later), the instructor plans as follows:

• When moving from student 1 to student n (the forward journey), he may call some of the encountered students to leave immediately. Their exit orders will be determined by the order in which they are called (which is necessarily in increasing order of their seat numbers).
• Any student not called in the forward journey will be called during the return journey (from student n back to student 1) in the order in which they are encountered. Their exit order will follow after those called in the forward journey.

If the instructor chooses to call exactly the first \(i\) students on the forward journey and the remaining students on the backward journey, then:

• For \(j = 1, \ldots, i\): \(r_j = j\).
• For \(j = i+1, \ldots, n\): \(r_j = i + (n - j + 1)\), because the backward call order is determined by the inverse of the seating order.

The task is to determine the maximum possible score the instructor can achieve over all valid strategies (i.e. for any \(i\) between 0 and \(n\), where \(i = 0\) means calling no one in the forward journey and \(i = n\) means calling everyone in the forward journey).

Note: It is always possible to call the students in such a way, and you only need to compute the maximum weighted score obtainable.

inputFormat

The input consists of two lines:

1. The first line contains a single integer \(n\) (\(1 \leq n \leq 10^5\)), the number of students.
2. The second line contains \(n\) integers \(w_1, w_2, \ldots, w_n\) (\(|w_i| \leq 10^9\)), representing the bad values of the students.

outputFormat

Output a single integer, the maximum possible score \(\sum_{i=1}^{n} r_i \times w_i\) the instructor can achieve.

sample

5
1 2 3 4 5

55