Windblume Festival Game

The Windblume Festival in Mondstadt is here and along with it comes a famous game invented by Jean, the Acting Grand Master of the Knights of Favonius. In the game, n players numbered from 1 to n stand in a circle, each holding an integer. In every turn, one player is removed until only one remains. At each turn the following process occurs:

• Let k be the current number of players and let a_i be the integer held by player i.
• Choose an index x (1 ≤ x ≤ k) arbitrarily. Then consider the two adjacent players x and (x mod k) + 1. The player (x mod k) + 1 is removed from the game.
• The integer held by player x is updated as
  \( a_x \leftarrow a_x - a_{(x \bmod k)+1} \).
• For every player with index y where x < y ≤ k, their index is decreased by 1 in the next round (their integer value remains unchanged).

Jean wants to know the maximum possible integer that the final remaining player can have if one chooses the index x optimally in each turn.

Observation: One may view the process as merging adjacent numbers on a circle via the binary operation a - b (which is non‐associative). Each full order of removals corresponds to a full parenthesization of an expression on a circular sequence of numbers. Using optimal parenthesization we want to maximize the final value.

In other words, for a given circular sequence \( a_1, a_2, \dots, a_n \), by choosing an optimal order of merging (where merging two adjacent numbers means replacing them with \( a - b \)), determine the maximum final number attainable.

inputFormat

The first line contains an integer n (1 ≤ n ≤ 300), representing the number of players.

The second line contains n space-separated integers \(a_1, a_2, \dots, a_n\) (\(|a_i| \le 10^9\)), denoting the integers held by each player in order.

outputFormat

Output a single integer, the maximum possible integer that can be obtained for the last remaining player after performing exactly n - 1 moves optimally.

sample

2
3 5

2