Description

bileo 在工作室刷题到深夜，准备一路跑回宿舍。

路上一共有 $n$ 个补给点，第 $i$ 个补给点有一瓶能量饮料，喝下后可以恢复 $a_i$ 点体力。

但是能量饮料喝多了会难受，所以相邻两个补给点的饮料不能同时喝。

bileo 想知道，他最多能恢复多少体力。

Format

Input

第一行输入一个整数 $n$ $(1 \le n \le 2 \times 10^5)$。

第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n$ $(1 \le a_i \le 10^9)$。

Output

输出一个整数，表示最大能恢复的体力值。

Samples

5
2 7 9 3 1

12

Limitation

1s, 1024KiB .