Có \(N\) cây táo được xếp thành một hàng, cây thứ \(i\) cho \(a_i\) quả táo. Bạn muốn chọn một số cây để hái táo sao cho không có hai cây nào được chọn đứng cạnh nhau. Hãy tìm số táo lớn nhất có thể hái được.

Input

• Dòng đầu tiên chứa một số nguyên \(N\). \((1 \le N \le 2 \cdot 10^5)\)
• Dòng thứ hai chứa \(N\) số nguyên \(a_1,a_2,\dots,a_N\). \((-10^9 \le a_i \le 10^9)\)

Output

• In ra một số nguyên duy nhất là số táo lớn nhất có thể hái được.

Example

5
3 2 7 10 1

13