A. 高高的数组

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

给你一个数组,其中的数值只有 1 -1 ,必须进行一次如下操作:

选择一个数组下标 (1<=i<n) , 分别把 a_i a_{i+1} 的值转换一下,

转换的意思是把 1 变成 -1 -1 变成 1

求该数组求和后的最大值是多少?

输入格式

第一行,输入一个 n (2≤n≤100000)

第二行,输入 n 个数 a_1,a_2, a_3,...a_i,...,a_n (a_i=1 或 -1)

输出格式

输出求和后的最大值

样例

输入样例1

2
1 -1

输出样例1

0

输入样例2

5
1 1 -1 -1 1

输出样例2

5