#F. 辰辰的步伐

    Type: Default 1000ms 256MiB

辰辰的步伐

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,31,2,3

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

Format

Input

第一行一个正整数 nn

第二行 nn 个正整数 aia_i,表示每个石子的美丽程度。

Output

一行一个整数,表示答案,即所以方案中的最短段的最小值,若无解,请输出 1-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

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

对于前十组数据,1n20,1ai1001\le n\le 20,1\le a_i\le 100

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