AT_abc162_f [ABC162F] Select Half

[problemUrl]: https://atcoder.jp/contests/abc162/tasks/abc162_f 長さ $ N $ の整数列 $ A_1,...,A_N $ が与えられます。 この中からちょうど $ \left\lfloor\ \frac{N}{2}\ \right\rfloor $ 個の整数を、どの $ 2 $ 箇所も連続しないように選びます。 選んだ要素の和としてありえる最大値を求めてください。 ここで、$ \lfloor\ x\ \rfloor $ は、$ x $ を超えない最大の整数を表します。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ ... $ $ A_N $

選ばれた要素の和としてありえる最大値を出力せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 2\times\ 10^5 $ - $ |A_i|\leq\ 10^9 $ - 入力は全て整数 ### Sample Explanation 1 $ 2,4,6 $ を選ぶと和は $ 12 $ となり、これが最大です。 ### Sample Explanation 2 $ -10,10 $ を選ぶと和は $ 0 $ となり、これが最大です。 ### Sample Explanation 3 オーバーフローに注意してください。