Mô tả

Một vườn táo có N cây được trồng thành một hàng thẳng. Cây thứ i có A_i quả táo.

Do các cây đứng quá gần nhau, nếu hái táo ở một cây thì không được hái ở hai cây liền kề với cây đó.

Hãy tính số lượng táo lớn nhất có thể thu hoạch.

Dữ liệu vào

Gồm:

Dòng đầu chứa số nguyên N.
Dòng thứ hai chứa N số nguyên A1 A2 ... AN.

Dữ liệu ra

In ra một số nguyên là số quả táo lớn nhất có thể thu hoạch.

Ràng buộc

1 ≤ N ≤ 10⁵

1 ≤ A_i ≤ 10⁹

Ví dụ

Input

4
3 2 7 10

Output

13

Giải thích

Có các cách chọn hợp lệ:

• Chọn cây 1 và cây 3: thu được 3 + 7 = 10.

• Chọn cây 2 và cây 4: thu được 2 + 10 = 12.

• Chọn cây 1 và cây 4: thu được 3 + 10 = 13.

Không thể chọn đồng thời cây 3 và cây 4 vì chúng kề nhau.

Vì vậy, số táo lớn nhất có thể thu hoạch là 13.