Cho dãy số nguyên \(A = (a_1, a_2, \dots, a_n)\). Một dãy con của dãy \(A\) được tạo ra bằng cách xóa đi một số phần tử của dãy \(A\) (có thể không xóa phần tử nào) và giữ nguyên thứ tự các phần tử còn lại.

Yêu cầu: Hãy tìm một dãy con của dãy \(A\) sao cho tổng các phần tử của dãy con đó là lớn nhất, với điều kiện trong dãy con không có hai phần tử nào đứng cạnh nhau trong dãy \(A\) ban đầu.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(n \le 10^6\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(|a_i| \le 10^9\)).

Output

• Một số nguyên duy nhất là tổng lớn nhất tìm được.

Example

5
-2 5 3 1 6

11

Scoring

• Có \(60\%\) số test ứng với \(60\%\) số điểm của bài có \(n \le 10^3\).
• Có \(40\%\) số test còn lại ứng với \(40\%\) số điểm của bài có \(n \le 10^6\).