#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/15/problems/D

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████

15D. Distant Transfers

2000 pts2s256 MB

You are given an array $a_1, a_2, \ldots, a_n$ of integers.

For a positive integer $k$ , you may perform the following operation any number of times:

Choose two indices $l$ and $r$ such that $1 \le l < r \le n$ and $r-l \ge k$ . Then decrease $a_l$ by $1$ and increase $a_r$ by $1$ .

Find the maximum integer $k$ with $1 \le k \le n-1$ such that it is possible to make every element of the array equal to $0$ .

If there is no such integer $k$ , output $-1$ .

Constraints

$2 \le n \le 2 \times 10^5$
$-10^9 \le a_i \le 10^9$

Input

n

a_1 \quad a_2 \quad \cdots \quad a_n

Output

ans

Samples

Input

2
1 -1

Explanation

Choosing indices $1$ and $2$ once changes the array to $0,0$ . Since $k$ cannot be larger than $n-1$ , the maximum possible value is $1$ .

Output

Input

2
-1 1

Explanation

The only possible operation would decrease the first element and increase the second element, so it cannot make the array equal to $0,0$ .

Output

-1

Input

5
3 0 -1 -2 0

Explanation

For $k=2$ , choosing $(1,3)$ once and $(1,4)$ twice makes all elements equal to $0$ . For $k=3$ , the third position cannot receive a unit from any position far enough to its left.

Output

Input

4
0 0 0 0

Explanation

The array is already all zero, so every $k$ from $1$ to $3$ is valid. The maximum one is $3$ .

Output

You are given an array $a_1, a_2, \ldots, a_n$ of integers.

For a positive integer $k$ , you may perform the following operation any number of times:

Choose two indices $l$ and $r$ such that $1 \le l < r \le n$ and $r-l \ge k$ . Then decrease $a_l$ by $1$ and increase $a_r$ by $1$ .

Find the maximum integer $k$ with $1 \le k \le n-1$ such that it is possible to make every element of the array equal to $0$ .

If there is no such integer $k$ , output $-1$ .

$2 \le n \le 2 \times 10^5$
$-10^9 \le a_i \le 10^9$

n

a_1 \quad a_2 \quad \cdots \quad a_n

ans

Choosing indices $1$ and $2$ once changes the array to $0,0$ . Since $k$ cannot be larger than $n-1$ , the maximum possible value is $1$ .

The only possible operation would decrease the first element and increase the second element, so it cannot make the array equal to $0,0$ .

For $k=2$ , choosing $(1,3)$ once and $(1,4)$ twice makes all elements equal to $0$ . For $k=3$ , the third position cannot receive a unit from any position far enough to its left.

The array is already all zero, so every $k$ from $1$ to $3$ is valid. The maximum one is $3$ .

Distant Transfers - Repovive Starter Round 4 | Repovive | Repovive

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

15D. Distant Transfers

Constraints

Input

Output

Samples

15D. Distant Transfers

Constraints

Input

Output

Samples