Vì vừa đạt giải cao trong một kì thi lập trình, bạn Quân được ban tổ chức trao thưởng. Ban tổ chức đã sắp xếp N món quà thành một hàng ngang, mỗi món quà có một giá trị nhất định. Thể lệ trao thưởng yêu cầu Quân phải chọn một tập hợp các món quà sao cho tổng giá trị là lớn nhất, với điều kiện không được chọn quá 2 món quà liên tiếp trong hàng.

Yêu cầu: Hãy giúp Quân tính toán tổng giá trị lớn nhất của các món quà mà bạn ấy có thể nhận được.

Input

Dòng đầu ghi một số nguyên N (1 <= N <= 10^5).
Dòng thứ hai ghi N số nguyên A_1, A_2, ..., A_N thể hiện giá trị của N món quà (0 <= |A_i| <= 10^6).

Output

In ra tổng giá trị các món quà lớn nhất mà bạn Quân có thể chọn.

Example

input
6
3 4 2 3 4 5

output
16