Rô bốt

Anna đang tham gia một vòng chung kết lập trình. Nhiệm vụ của cô là lập trình để nạp phần mềm cho \(n\) con rô-bốt hoạt động.
Các rô-bốt được đánh số từ \(1\) đến \(n\).

Mỗi rô-bốt khi hoạt động sẽ nhận một giá trị là \(+1\) hoặc \(-1\).
Sau khi toàn bộ \(n\) rô-bốt hoạt động, hệ thống ghi nhận được một dãy giá trị
$
a_1, a_2, \ldots, a_n
$
trong đó \(a_i \in \{1, -1\}\) là giá trị của rô-bốt thứ \(i\).

Tiếp theo, hệ thống cho phép Anna thực hiện tối đa một lần thao tác sau:

• Chọn một chỉ số \(i\) \((1 \le i < n)\) và đổi dấu giá trị của rô-bốt thứ \(i\) và rô-bốt thứ \(i+1\) (tức là nếu giá trị đang là \(1\) thì chuyển thành \(-1\), và ngược lại).

Yêu cầu:
Hãy chọn cách thực hiện thao tác (hoặc không thực hiện thao tác nào) sao cho tổng giá trị của \(n\) rô-bốt là lớn nhất.

Input

Dòng đầu chứa số nguyên dương \(n\) \((1 \le n \le 10^6)\).

Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,\ldots,a_n\) với \(a_i \in \{1, -1\}\).

Output

In ra một số nguyên duy nhất là tổng giá trị lớn nhất có thể đạt được.

Scoring

• Subtask 1 (60 points): \(1 \le n \le 10^3\).
• Subtask 2 (40 points): \(10^3 < n \le 10^6\).

Sample Input 1

5
-1 1 1 -1 -1

Sample Output 1

3

Sample Input 2

2
1 1

Sample Output 2

2