Bob is taking a course on typography, the art of arranging words! In this course, he is given a phrase with words consisting only of English letters. He must split the phrase over one or more lines, and he cannot split the phrase in the middle of a word.

For example, he can split `the quick brown fox jumps over the lazy dog`

over four lines like this:

```
the quick brown
fox jumps
over
the lazy dog
```

As any good typographer knows, a split is **pretty** if the number of letters in each line (not including spaces) form:

- a non-increasing sequence,
- a non-decreasing sequence,
- or a non-increasing then non-decreasing sequence.

More rigorously, let be the total number of lines and be the number of letters in line . Then a split is pretty if there exists such that and .

For example, the following splits are pretty:

```
the
quick brown
fox jumps over the lazy dog
```

```
the quick brown
fox jumps
over
the lazy dog
```

`the quick brown fox jumps over the lazy dog`

And the following split is not:

```
the quick
brown fox jumps
over the lazy
dog
```

Over all pretty splits, please help Bob find the one with the maximum number of lines!

#### Constraints

Each word contains at least and no more than letters.

##### Subtask 1 [2/15]

##### Subtask 2 [3/15]

##### Subtask 3 [3/15]

##### Subtask 4 [6/15]

##### Subtask 5 [1/15]

#### Input Specification

The first line contains , the number of words in the phrase.

The second line contains space-separated integers, the number of letters in each word.

#### Output Specification

The number of lines in the longest possible pretty split.

#### Sample Input

```
9
3 5 5 3 5 4 3 4 3
```

#### Sample Output

`6`

#### Explanation for Sample Input

This input corresponds to the phrase given in the problem description. One longest pretty split for that phrase is:

```
the quick
brown
fox
jumps
over the
lazy dog
```

with 6 lines.

## Comments