P9097 [PA 2020] Elektrownie i fabryki

**题目译自 [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/)** 为了应对不断上升的失业率，Byteotia 政府决定创造新的就业机会。为此将建设现代化的工厂，还要建设为工厂供电的新发电厂。 一条很长的高速公路穿过 Byteotia，沿途有 $n$ 个城市。为了简单起见，我们从 $1$ 到 $n$ 对城市进行编号。每两个相邻城市之间都相距一公里。 目前已经决定一些城市建设工厂，另一些城市建设发电厂。对于第 $i$ 个城市有一个值 $a_i$。如果它是正数，则在第 $i$ 个城市将建造一个发电容量为 $a_i$ 兆瓦的发电厂，如果它是负数，则在该城市将建造一个消耗电能 $a_i$ 兆瓦的工厂。如果 $a_i=0$，则说明该城市没有建设计划。 你的任务是设计一个电网，将电力从发电站输送到工厂。对于每一对相邻的城镇，你必须决定是否在它们之间建立一条输电线。如果这个城市被输电线直接或间接连接到某个有发电站的城市，电力就可以从发电站流向这个城市的工厂。如果每个工厂的电力需求都得到满足，那么电网的设计就是正确的。电网的成本与电网输电线的总长度（以公里计）成正比。 写一个程序计算设计一个正确的电网最小成本是多少。

第一行一个整数 $n$，表示 Byteotia 的城市个数。 第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$，表示每个城市电力的生产和消耗。

输出设计一个正确的电网的最小成本。如果不存在一个正确的电网，输出 $-1$。

#### 样例 1 解释 下面是一个包含 $n=17$ 个城市的样例，其中将建造三个工厂（白圈）和四个发电厂（黑圈）。$12$ 公里的正确电网用灰色部分标记。  ------------ #### 数据范围 **本题采用捆绑测试** 对于一些子任务，满足 $n\le 5\times 10^3$。 对于 $100\%$ 的数据，保证 $1\le n\le 5\times 10^5$，$-10^9\le a_i\le 10^9$。