An cũng thích chơi trò chơi trên máy tính, có nhiều trò chơi đòi hỏi thông minh nên không dễ như ăn bánh. Có một trò chơi thu thập năng lượng như sau: Có một dãy ô gồm ~N~ ô vuông, các ô được đánh số từ ~1~ đến ~N~ theo thứ tự từ trái sang phải, ô ~i~ có năng lượng là ~A_i~. Quy tắc để thu thập năng lượng như sau:

• Năng lượng ban đầu là ~0~.
• Lần lượt chọn các ô theo thứ tự từ trái sang phải.
• Nếu lần chọn thứ ~k~ là ô ~j~ thì năng lượng được tăng thêm ~A_i~ (~k~ là số lẻ) hoặc giảm đi ~A_i~ (~k~ là số chẵn).

Người chơi cần xác định cách chọn các ô sao cho tổng năng lượng thu thập được là lớn nhất có thể.

Yêu cầu

Cho biết ~N~ và năng lượng tương ứng trên từng ô là ~A_1, A_2, ..., A_N~. Hãy xác định tổng năng lượng lớn nhất mà An có thể đạt được khi chơi trò chơi được mô tả ở trên.

Dữ liệu đầu vào

Gồm nhiều dòng ứng nhiều bộ dữ liệu cần xác định trong trò chơi, dòng thứ ~i~ chứa thông tin của một bộ dữ liệu thứ ~i~: số đầu tiên là ~N~ (số ~N~ nguyên dương), tiếp theo là ~N~ số nguyên dương ~A_1, A_2, ..., A_N~ ~(1 \le A_i \le 10^4)~ tương ứng là năng lượng trên từng ô.

Dữ liệu đầu ra

Gồm nhiều dòng, dòng thứ ~i~ chứa một số nguyên là tổng năng lượng lớn nhất có thể đạt được theo yêu cầu tương ứng bộ dữ liệu thứ ~i~ trong dữ liệu vào.

Ràng buộc dữ liệu

• Có 75% số test có một bộ dữ liệu vào và ~N \le 10^4~.
• Có 25% số test có hơn một bộ dữ liệu vào và ~1 \le N \le 10^5~.

Ví dụ

Ví dụ 1

INPUT

4 3 1 4 9
3 3 1 4

OUTPUT

11
6