$N$ 個の石の山があり、はじめ $i$ 番目の山には石が $A_i$ 個あります。これらの山を使って先手橋くんと後手木くんがゲームをします。
先手橋くんを先手として交互に次の操作を行います。

• 操作する前の時点での山の数を $M$ とする。整数 $i, x, y$ を $1 \leq i \leq M, x \in \{ 0,1 \}, 1 \leq y < A_i - x$ となるように決める。
• $x = 1$ なら山 $i$ から石を一つ選び、食べる。
• 残った $A_i - x$ 個の石から $y$ 個の石を選び新しい山 $M+1$ として置く。以降の操作では $A_{M+1} = y$ とする。

条件を満たすように $i, x, y$ を決めることができない場合ゲームに負け、負けなかったほうが勝ちます。
両プレイヤーはゲームに勝ったとき $2$ のうれしさを得ます。また、$1$ 番目の山には $1$ つだけおいしい石があり、これを食べることができた場合 $1$ のうれしさを得ます。

先手橋くんと後手木くんのゲーム終了時のうれしさをそれぞれ $F, S$ としたとき、
先手橋くんは $F - S$ を最大化、後手木くんは最小化するよう最適な行動をとります。
このときの $F - S$ の値を求めてください。

• $1 \leq N \leq 5 \times 10^5$
• $1 \leq A_i \leq 10^9$
• 入力はすべて整数である。

この問題には、部分点が設定されている。部分点の採点方法については、コンテストトップ を参照すること。

1. ($300$ 点)

• $1 \leq A_i \leq 5000$

1. ($300$ 点)

• 追加の制約はない。

入力は以下の形式で標準入力から与えられる。

$F - S$ の値を出力せよ。