Ngày xửa ngày xưa, Gấu Trắng là một thần dân trong Thế Giới Âm Nhạc – vương quốc được điều phối bởi sức mạnh của những thanh tấu, giai điệu. Nơi đây, tồn tại một thực thể tối thượng mang tên Quả Cầu Âm Thanh. Nó là thứ báu vật vô song, chỉ được chinh phục, sở hữu bởi một cá nhân xuất chúng mỗi hàng trăm thế hệ, và là biểu tượng tối cao của sự xứng đáng, được công nhận bởi thần dân của cả quá khứ, hiện tại, tương lai trong Vương Quốc Âm Nhạc. Và nó đã trong trạng thái vô chủ trong suốt hàng nghìn năm nay!

Để sở hữu Quả Cầu Âm Thanh, một thần dân cần phải có khả năng vượt ải diệt boss, chiến đấu với quái vật, thể hiện và chứng minh tài năng của bản thân với tất cả công dân trong vương quốc, và cuối cùng, tấu được khúc Giai Điệu Ngàn Năm – khúc nhạc huyền thoại, là chìa khóa cuối cùng trong hành trình chinh phục Quả Cầu Âm Thanh. Nghe nói… trong chính cái tên của giai điệu này, ẩn chứa một sức mạnh nghịch đảo khủng khiếp…

Với khát vọng chinh phục Quả Cầu Âm Thanh, Gấu Trắng quyết định chuẩn bị hành trang cho chuyến phiêu du của mình. Để nghiên cứu về Giai Điệu Ngàn Năm, cậu nhận ra mình cần rất nhiều kỹ năng và tư duy giải quyết vấn đề. Gấu Trắng quyết định bắt đầu luyện tập bằng bài toán sau:

Gấu được cho một dãy số ~a~ gồm ~N~ phần tử, phần tử thứ ~i~ có giá trị là ~a_i~. Gấu sẽ phải lựa ra một dãy con của dãy ~a~. Một dãy con ~k~ phần tử của dãy ~a~ được định nghĩa là dãy ~a_{i_1}, a_{i_2}, \ldots, a_{i_k}~ ~(1 \le i_1 < i_2 < ... < i_k \le N)~. Tổng của dãy con ~k~ phần tử mà Gấu chọn sẽ là ~a_{i_1} + a_{i_2} + \ldots + a_{i_k}~ . Tìm dãy con có số lượng phần tử là lẻ, sao cho tổng của dãy con này là lớn nhất.

Input

• Dòng đầu chứa số ~N~ ~(1 \le N\le 10^6)~.

• Dòng tiếp theo chứa ~N~ số nguyên ~a_1,a_2,\ldots,a_N~ ~(|a_i| \leq 10^9)~.

Output

Một số duy nhất là đáp án của bài toán: tổng lớn nhất của một dãy con có lẻ phần tử.

Scoring

• Subtask ~1~ (~18\%~): ~n \leq 20~.

• Subtask ~2~ (~14\%~): ~\min(a_1,a_2,\ldots,a_n) = \max(a_1,a_2,\ldots,a_n)~.

• Subtask ~3~ (~23\%~): ~a_i \geq 0~ ~(1 \leq i \leq n)~.

• Subtask ~4~ (~21\%~): ~a_1 \geq a_2 \geq \ldots \geq a_n~.

• Subtask ~5~ (~24\%~): Không có giới hạn gì thêm.

Sample Input 1

6
-1 2 -3 -1 -2 4

Sample Output 1

5

Notes

Chọn ~3~ phần tử ~a_2, a_4, a_6~ có giá trị ~2 + (-1) + 4 = 5~.