Description

给定一个长度为n且仅包含1、0、1的数列a，接下来进行若干次操作，每次操作可以选择一个下标，将a_i设为a_i与a_i-1的和，请计算最少需要操作多少次才能使数列a中每一个元素都大于等于前一项元素（第一项元素除外）；如果无法通过操作满足次条件，则输出-1。 例如：n=6，数列a为{ -1,1,0,-1,0,1};操作过程如下： 1、a₁=a₁+a₀=0,数列变为{-1,0，0，-1,0,1}； 2、a₁=a₁+a₀=-1，数列变为{-1，-1,0，-1,0,1}； 3、a₂=a₂+a₁=-1，数列变为{-1，-1，-1，-1,0,1}； 此时数列a中每一项元素都大于等于前一项元素（第一项元素除外），且没有更好的操作方案，故最少需要操作3次。

Format

Input

第一行包含一个整数n; 第二行包含n个整数a₀，a₁,a₂,...,a_n-1,整数之间以一个空格隔开。

数据范围： 测试点1~10： 1<=n<=10⁵,-1<=a_i<=1。

Output

一个整数，表示使数列a中每一项元素都大于等于前一项元素（第一项元素除外）的最少操作次数；如果无法通过操作满足次条件，则输出-1。

Samples

6
-1 1 0 -1 0 1

3

3
0 -1 1

-1

Limitation

1s, 1024KiB for each test case.