Bạn là một tên trộm chuyên nghiệp đang lên kế hoạch trộm các ngôi nhà dọc theo một con phố. Mỗi ngôi nhà có một lượng tiền nhất định. Ràng buộc duy nhất là các ngôi nhà liền kề có hệ thống an ninh kết nối với nhau và sẽ tự động báo cảnh sát nếu hai ngôi nhà liền kề bị đột nhập trong cùng một đêm.

Input

• Dòng đầu tiên chứa một số nguyên n, là số lượng ngôi nhà.
• Dòng thứ hai chứa n số nguyên a1, a2, ..., an, mỗi số là lượng tiền trong ngôi nhà tương ứng

Output

In ra một số nguyên duy nhất là số tiền tối đa bạn có thể trộm được mà không bị báo động.

Ví dụ

Ví dụ 1

Input:
4
1 2 3 1

Output:
4

Giải thích: Trộm nhà 1 (1) và nhà 3 (3) → tổng = 1 + 3 = 4.

Ví dụ 2

Input:
5
2 7 9 3 1

Output:
12

Giải thích: Trộm nhà 1 (2), nhà 3 (9) và nhà 5 (1) → tổng = 2 + 9 + 1 = 12.

Ràng buộc

• 1 ≤ n ≤ 100
• 0 ≤ ai ≤ 400