問題文

$2N$ 枚のカードが横一列に並んでいて、左から $i$ 枚目のカードには整数 $A_i$ が書かれています。
ほむらちゃんはてんぷらくんと次のようなゲームをして遊ぼうと思っていました。

1. ほむらちゃんがその時点で列に残っているカードのうち、左端または右端のカードを $1$ 枚選び、 書かれている数を点数として獲得する。選んだカードは破棄する。
2. てんぷらくんがその時点で列に残っているカードのうち、左端または右端のカードを $1$ 枚選び、 書かれている数を点数として獲得する。選んだカードは破棄する。
3. $1,2$ を $N$ 回繰り返す。
4. $N$ 回で獲得した点数の合計の大きいほうが勝ち。

入力

$N$
$A_1{A}_2\cdots A_{2N}$

• 入力はすべて整数
• $1\le N\le 100000$
• $1\le A_i\le {10}^9$

出力

(ほむらちゃんの獲得した点数の合計)$-$(てんぷらくんの獲得した点数の合計) として考えられる最大値を出力してください。 最後に改行してください。

サンプル

2
3 1 2 4

4

1
5 5

0

5
3 1 4 1 5 9 2 6 5 3

11