Cho một số nguyên dương ~n~ và dãy gồm ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~. Một "dãy con không kề nhau" là dãy được tạo ra bằng cách chọn ra một số phần tử của dãy sao cho không có hai phần tử nào được chọn có vị trí ban đầu kề nhau.

Hãy chọn ra một dãy con không kề nhau sao cho thỏa mãn hai điều kiện sau:

• Tổng các phần tử được chọn là một số lẻ;

• Tổng các phần tử được chọn là lớn nhất có thể.

Input

• Dòng ~1~ chứa số nguyên dương ~n~ ~(1 \le n \le 10^5)~;

• Dòng ~2~ chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le 10^9, i = 1, 2, \dots, n)~.

Output

Một số nguyên là tổng lẻ lớn nhất tìm được. Nếu không tìm được dãy con thỏa mãn, xuất ~-1~.

Scoring

Sample Input 1

5
2 3 4 5 1

Sample Output 1

7

Notes

Chọn dãy ~\{2, 4, 1\}~ có tổng lẻ và không có hai phần tử được chọn nào kề nhau. Đây là dãy có tổng lớn nhất thỏa mãn.