Có ~n~ ngôi nhà nằm trên một hàng. Mỗi ngôi nhà thứ ~i~ có một lượng tiền là ~a_i~. Bạn là một tên trộm thông minh - không thể trộm hai nhà kề nhau, vì như vậy sẽ bị phát hiện. Hãy tìm số tiền lớn nhất bạn có thể trộm được

Yêu cầu: Tính giá trị lớn nhất của tổng tiền có thể lấy, sao cho không có hai ngôi nhà nào kề nhau đều bị trộm.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \leq n \leq 10^6~)- số lượng ngôi nhà.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1,a_2,...,a_n~ , ~a_i~ (~1 \leq i \leq n,1 \leq a_i \leq 10^9~) là số tiền trong từng ngôi nhà.

Output

Một số nguyên dương duy nhất là số tiền lớn nhất mà bạn có thể trộm được.

Scoring

• Subtask ~1~ ~(30\%)~: ~n \leq 20, 1 \leq a_i \leq 1000~;
• Subtask ~2~ ~(70\%)~: ~n \leq 10^6, 1\leq a_i \leq 10^9~.

Example input 1

5
2 7 9 3 1

Example output 1

12

Note 1

• Tên trộm lấy tiền ở nhà số 2 và 4 → ~7 + 3 = 10~.
• Nhưng tốt hơn là nhà ~2~ và ~3 → 7 + 9 = 16~ (sai vì kề nhau).
• Đúng tối ưu là nhà ~2~ và ~5 → 7 + 1 = 8~ hoặc nhà ~1 + 3 + 5 = 2 + 9 + 1 = 12~.

→ Đáp án: ~12~.