Rô bốt

Anna đang dự thi vòng chung kết lập trình. Nhiệm vụ của Anna là phải lập trình để nạp phần mềm cho $n$ con Robot hoạt động, các con Robot được đánh số từ 1 đến $n$. Mỗi con Robot khi hoạt động được nó sẽ nhận một trong hai giá trị là 1 hoặc -1.

Sau khi toàn bộ $n$ con Robot đã hoạt động, hệ thống sẽ hiển thị một dãy $n$ giá trị $a_1, a_2, \dots, a_n$ ($a_i = 1$ hoặc $a_i = -1$) tương ứng với giá trị của từng con Robot.

Tiếp đến hệ thống sẽ chọn ngẫu nhiên con Robot thứ $i$ bất kì và tiến hành thay đổi giá trị của Robot thứ $i$ và thứ $i + 1$ (Nếu giá trị là -1 thì chuyển thành 1 và ngược lại), việc này chỉ thực hiện duy nhất một lần.

Yêu cầu: Hãy cho biết với các cách chọn con Robot thứ $i$ và thứ $i + 1$ $(i < n)$ để thay đổi giá trị như vậy thì tổng giá trị lớn nhất có thể đạt được của $n$ con Robot là bao nhiêu?

Dữ liệu: Đọc từ file văn bản ROBOT.INP gồm:

• Dòng đầu tiên ghi số nguyên dương $n$ $(n \le 10^6)$ là số lượng con Robot.
• Dòng thứ 2 gồm $n$ số nguyên $a_1, a_2, \dots, a_n$ $(a_i \in \{1, -1\})$ biểu thị giá trị tương ứng của từng con Robot.

Kết quả: Ghi ra file văn bản ROBOT.OUT tổng giá trị lớn nhất của $n$ con Robot có thể đạt được sau chuyển đổi.

• 60% số test với $1 \le n \le 10^3$;
• 40% số test với $10^3 < n \le 10^6$.