You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

辰辰正在小路上走着，忽然，他停下了脚步，他猛地向前一跳，跳入了一个洞，里面有着一排美丽的石子。

Description

有一排美丽的石子，每一个石子有一个美丽程度，辰辰要将其划分成连续的几段，在所有划分方案中，找出满足每一段石子的美丽程度和相同的情况下，最短的段长度。

例如，有一个序列 $1,2,3$。

我们这么划分 $1,2\ |\ 3$，这样第一段和第二段 $1+2=3$，其中第一段长度为 $2$，第二段长度为 $1$，所以答案为 $1$。

Format

Input

第一行一个正整数 $n$。

第二行 $n$ 个正整数 $a_i$，表示每个石子的美丽程度。

Output

一行一个整数，表示答案，即所以方案中的最短段的最小值，若无解，请输出 $-1$。

Samples

3
1 2 3

1

6
1 1 4 5 1 4

6

8
1 3 2 2 1 1 1 1

2

Limitation

本题数据共十二组，其中前十组有分，后两组无分。

对于前十组数据，$1\le n\le 20,1\le a_i\le 100$

对于后两组数据，$1\le n\le 10^5,1\le a_i\le 100$