题目描述

题目译自 PA 2020 Runda 2 Elektrownie i fabryki

为了应对不断上升的失业率，Byteotia 政府决定创造新的就业机会。为此将建设现代化的工厂，还要建设为工厂供电的新发电厂。

一条很长的高速公路穿过 Byteotia，沿途有 $n$ 个城市。为了简单起见，我们从 $1$ 到 $n$ 对城市进行编号。每两个相邻城市之间都相距一公里。

目前已经决定一些城市建设工厂，另一些城市建设发电厂。对于第 $i$ 个城市有一个值 $a_i$。如果它是正数，则在第 $i$ 个城市将建造一个发电容量为 $a_i$ 兆瓦的发电厂，如果它是负数，则在该城市将建造一个消耗电能 $a_i$ 兆瓦的工厂。如果 $a_i=0$，则说明该城市没有建设计划。

你的任务是设计一个电网，将电力从发电站输送到工厂。对于每一对相邻的城镇，你必须决定是否在它们之间建立一条输电线。如果这个城市被输电线直接或间接连接到某个有发电站的城市，电力就可以从发电站流向这个城市的工厂。如果每个工厂的电力需求都得到满足，那么电网的设计就是正确的。电网的成本与电网输电线的总长度（以公里计）成正比。

写一个程序计算设计一个正确的电网最小成本是多少。

输入格式

第一行一个整数 $n\ (1\le n\le 5\times 10^5)$，表示 Byteotia 的城市个数。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n\ (-10^9\le a_i\le 10^9)$，表示每个城市电力的生产和消耗。

输出格式

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

17
2 -5 0 2 0 0 0 4 0 0 -1 4 0 0 0 0 -3

12

数据范围与提示

对于一些子任务，满足 $n\le 5\times 10^3$。