Farmer John の牛たちは大好きな童謡の牛のように月を飛び越えたいと思っています。残念ながら牛は跳べません。
地元の呪術医は跳躍を助ける $P$ 個の薬（$1 \le P \le 150{,}000$）を作りました。作成順に厳密に飲む必要がありますが、一部は飛ばせます。
各薬には跳躍能力を高める「強さ」（$1 \le strength \le 500$）があります。奇数の時刻で飲むと跳躍が増え、偶数の時刻では減ります。飲む前の能力はもちろん0です。
同じ薬を2回飲めません。飲み始めたら時刻1から各時刻に一つ飲む必要があります。各回に一つ以上の薬を飛ばせます。
最も高く跳べるよう、飲む薬を決めてください。
入力
- $1$ 行目：整数 $P$。
- $2..P+1$ 行目：各行は薬の強さを表す整数です。2行目は最初、3行目は2番目の強さで、以下同様です。
出力
- $1$ 行目：最大の跳躍を表す整数一つ。
入出力例
入力 1
8 7 2 1 8 4 3 5 6
出力 1
17