Khu phố ABZ có \(n\) ngôi nhà, mỗi ngôi nhà đều có một giá trị tài sản nhất định. Một tên siêu trộm đã lẻn được vào khu phố. Với tính cẩn thận nên với mỗi ngôi nhà, hắn có thể lựa chọn trộm hoặc bỏ qua, sao cho trong các ngôi nhà hắn đã trộm không có quá 2 ngôi nhà liên tiếp nhau. Hãy tính thiệt hại nhiều nhất mà khu phố có thể sẽ phải gánh chịu, biết rằng khi quyết định trộm ngôi nhà nào, hắn sẽ lấy toàn bộ tài sản của ngôi nhà đó.

Dữ liệu vào:

• Dòng 1: Ghi số nguyên dương \(n\) (\(n ≤ 2 × 10^{5}\)).
• Dòng 2: Ghi n số nguyên ai đại diện cho tài sản của từng ngôi nhà (\(1 ≤ i ≤ n\); \(1 ≤ a_i ≤ 10^{6}\)).

Kết quả

• Một dòng duy nhất là thiệt hại tối đa của khu phố.

Giới hạn

• 30% số test có n ≤ 20;
• 30% số test có \(a_1 = a_2 = … = a_n\);
• 40% số test còn lại không có ràng buộc gì thêm.

Ví dụ:

5
2 9 10 3 5

24