#44. 网络牛

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

题目描述

等蹦蹦炸弹爆炸的浓烟散去后,猫猫冒险队发现前方站着两位少女,其中一位少女背着一背包的炸弹。

另一位白发少女走到橙子面前说道:“你好,我叫 Kiana ,我的队友 EricJCKoishi 大魔王施法变成小可莉了,她现在遇到人就会乱扔炸弹,唉。

我现在在想办法把 EricJC 恢复原样,所以我尝试黑入 Koishi 城堡的网络寻找关于这种魔法的数据,你可以帮帮我吗?”

众所周知,黑客想黑入别人的网络就必须解决著名的网络牛问题,网络牛问题需要你求出这个网络的最大牛和最小鸽。

因为 Koishi 的网络只有一根网线,所以网络上的牛和鸽子都在一个一维的线上。

Koishi 的网络上牛和鸽子的总数一共有 只。

Kiana 可以选择网络中任意一头牛,然后让它往左或往右冲锋,牛会把路径上所有牛和鸽子都撞出网络,最后自己也会冲出网络。

Kiana 仅能选择一头牛,且不能不选,网络里保证至少存在一头牛。

Kiana 需要算出选择哪头牛往哪个方向冲锋会使得网络上( 牛的总数-鸽子总数 )这个式子的答案最大。

因为每个黑客解决这个问题都想让牛的数量尽量多,鸽子数量尽量少,所以才有最大牛和最小鸽这两个黑客专业术语( 全篇在乱扯,请勿当真 )。

输入格式

第一行输入一个整数 。代表网络里牛和鸽子的总数一共有 只。

接下来一行输入 个整数,其中 代表牛, 代表鸽子。

输出格式

输出一个整数 ,代表选择一头牛冲锋后,( 牛的总数-鸽子总数 )这个式子的最大答案。

样例

输入样例

5 
0 1 0 0 1 

输出样例

0

数据范围与提示

让第一头牛向左冲锋的答案是 -1

让第一头牛向右冲锋的答案是 -1

让第二头牛向左冲锋的答案是 0

让第二头牛向右冲锋的答案是 -2

因此最终答案是 0