Dãy con

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ể.

Dữ liệu vào

• 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)$.

Dữ liệu ra

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$.

Ràng buộc

• $1\le n\le {10}^5$.
• $1\le a_i\le {10}^9$.

Subtasks

• Subtask 1 ($25\%$ số điểm): $n\le 20$.
• Subtask 2 ($35\%$ số điểm): $n\le 2000$, $a_i\le 1000$.
• Subtask 3 ($40\%$ số điểm): Không có thêm ràng buộc bổ sung.

Ví dụ