Dũng và Vũ là hai bạn thân rất mê toán. Đôi bạn thường nghĩ ra các bài toán để chơi igiair trí với nhau. Hôm nay Vũ nghĩ ra một trò chơi mới và mời Dũng cùng chơi. Trò chơi Vũ đề ra như sau: Vũ viết lần lượt n số nguyên a1 , a2 , ... , an thành một hàng, sau đó giữa số ai và ai+1 sẽ điền vào dấu + khi i là số chẵn, ngược lại điền dấu - . Như vậy Vũa sẽ có một biểu thức gồm n số hạng a1 , a2 , ..., an với dấu - và + đan xen nhau:
a1 - a2 +a3 - a4 +a5 - ... + an
Vũ đưa cho Dũng biểu thức này và yêu cầu Dũng thực hiện nhiều nhất một phép đổi chỗ hai số hạng cho nhau so cho giá trị của biểu thức nhận được lớn nhất có thể.
Yêu cầu: Hãy giúp Dũng tìm giá trị của biểu thức.
Giới hạn: n<= 106; |ai| <= 109 với mọi i=1,2, ... , n