为了应对日益增长的失业率，Bajtocja 政府决定创造新的就业岗位。为此，政府将建造现代化的工厂，以及为工厂提供电能的新发电站。

Bajtocja 被一条长长的公路贯穿，沿途坐落着 $n$ 座城市。为简化起见，我们将城市编号为 $1$ 到 $n$。每相邻两座城市之间的距离为一个“千字节米”（kilobajtometr）。

相关决策已经做出：部分城市将建立工厂，部分城市将建立发电站。对于第 $i$ 座城市，我们已知其数值 $a_i$。如果 $a_i$ 为正，则第 $i$ 座城市将建立一座功率为 $a_i$ 兆瓦的发电站；如果 $a_i$ 为负，则该城市将建立一座消耗 $-a_i$ 兆瓦电能的工厂。如果 $a_i = 0$，则该城市不计划进行任何建设。

你的任务是设计一个电网，将电能从发电站输送到工厂。对于每一对相邻的城市，你需要决定是否在它们之间铺设一段电网。如果发电站和工厂所在的城市通过电网段直接或间接相连，电能就可以从发电站流向工厂。当每一座工厂的用电需求都得到满足时，该电网即被视为设计正确。电网的成本与电网段的总长度（以千字节米为单位）成正比。

请编写一个程序，设计出成本最低的正确电网。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 500\,000$)，表示 Bajtocja 的城市数量。

第二行包含一个由 $n$ 个整数组成的序列 $a_1, \dots, a_n$ ($-10^9 \le a_i \le 10^9$)，表示各城市建筑的能源生产或消耗情况。

输出格式

输出一行，包含正确电网的最小成本。如果不存在任何合法的电网，则输出 $-1$。

样例

样例输入 1

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

样例输出 1

12

说明 1

下图展示了包含 $n = 17$ 座城市的测试样例，其中将建造三座工厂（白色圆圈）和四座发电站（黑色圆圈）。图中还标出了长度为 12 千字节米的正确电网（灰色线段）。

样例说明图

子任务

在部分测试组中，$n \le 5000$。