{"raw_statement":[{"iden":"statement","content":"**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 2 [Elektrownie i fabryki](https://sio2.mimuw.edu.pl/c/pa-2020-1/p/ele/)**\n\n为了应对不断上升的失业率，Byteotia 政府决定创造新的就业机会。为此将建设现代化的工厂，还要建设为工厂供电的新发电厂。\n\n一条很长的高速公路穿过 Byteotia，沿途有 $n$ 个城市。为了简单起见，我们从 $1$ 到 $n$ 对城市进行编号。每两个相邻城市之间都相距一公里。\n\n目前已经决定一些城市建设工厂，另一些城市建设发电厂。对于第 $i$ 个城市有一个值 $a_i$。如果它是正数，则在第 $i$ 个城市将建造一个发电容量为 $a_i$ 兆瓦的发电厂，如果它是负数，则在该城市将建造一个消耗电能 $a_i$ 兆瓦的工厂。如果 $a_i=0$，则说明该城市没有建设计划。\n\n你的任务是设计一个电网，将电力从发电站输送到工厂。对于每一对相邻的城镇，你必须决定是否在它们之间建立一条输电线。如果这个城市被输电线直接或间接连接到某个有发电站的城市，电力就可以从发电站流向这个城市的工厂。如果每个工厂的电力需求都得到满足，那么电网的设计就是正确的。电网的成本与电网输电线的总长度（以公里计）成正比。\n\n写一个程序计算设计一个正确的电网最小成本是多少。"},{"iden":"input","content":"第一行一个整数 $n$，表示 Byteotia 的城市个数。\n\n第二行 $n$ 个整数 $a_1,a_2,\\cdots,a_n$，表示每个城市电力的生产和消耗。"},{"iden":"output","content":"输出设计一个正确的电网的最小成本。如果不存在一个正确的电网，输出 $-1$。"},{"iden":"note","content":"#### 样例 1 解释\n\n下面是一个包含 $n=17$ 个城市的样例，其中将建造三个工厂（白圈）和四个发电厂（黑圈）。$12$ 公里的正确电网用灰色部分标记。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/2wee5eoz.png)\n\n------------\n\n#### 数据范围\n\n**本题采用捆绑测试**\n\n对于一些子任务，满足 $n\\le 5\\times 10^3$。\n\n对于 $100\\%$ 的数据，保证 $1\\le n\\le 5\\times 10^5$，$-10^9\\le a_i\\le 10^9$。"}],"translated_statement":null,"sample_group":[["17\n2 -5 0 2 0 0 0 4 0 0 -1 4 0 0 0 0 -3","12"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}