Distant Transfers - Repovive Starter Round 4 | Repovive

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$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

15D. Distant Transfers

Constraints

Input

Output

Samples

15D. Distant Transfers

Constraints

Input

Output

Samples