Branding is the process of applying a permanent, unique identifying mark to an animal for tracking purposes. Farmer Patrick owns ~n~ bulls standing in a circular pen, where each bull ~i~ has an inherent "vanity" ~V_i~. Patrick plans to brand all of his bulls, starting from any one bull and proceeding clockwise around the circle until all ~n~ are branded.

His branding device, the "bullshit brander", alternates between making cool and uncool designs:

• The first design gives the bull a swag of ~+n~.
• The second design gives the bull a swag of ~-(n-1)~.
• The third gives ~+(n-2)~.
• The fourth gives ~-(n-3)~.

This pattern continues, alternating in sign and decreasing in until all bulls are branded. Formally, the ~k~-th bull branded (where ~k~ starts from ~1~) receives swag equal to:

~(-1)^{k-1} \times (n-k+1)~

The "confidence" that a bull ~i~ has is the product of its vanity and swag. How can Patrick brand his bulls to maximise the sum of their confidence?

Input

The first line contains an integer ~n~ ~(2 \leq n \leq 10^5)~, the number of bulls to be branded. ~n~ is even.

The next line contains ~n~ space-separated integers ~V_1, ..., V_n~ ~(1 \leq V_i \leq 10^5)~, where ~V_i~ represents the vanity of the ~i~th bull.

Output

Given that Patrick can begin from any arbitrary bull, Output the maximum confidence gained by branding all bulls in order.

Example

Input 1

4
1 5 8 4

Output 1

17

There are 4 ways that Patrick can brand the bulls:

By starting with the 3rd bull, Patrick can give:

• The third bull a swag of ~4~. His confidence is ~8 \times 4 = 32~.
• The fourth bull a swag of ~-3~. His confidence is ~4 \times -3 = -12~.
• The first bull a swag of ~2~. His confidence is ~1 \times 2 = 2~.
• The second bull a swag of ~-1~. His confidence is ~5 \times -1 = -5~.

The sum of all the bulls' confidence is ~32 - 12 + 2 - 5 = 17~, which is the maximum for any bull he can start with.