Bob is taking a course on typography, the art of arranging words! In this course, he is given a phrase with ~N~ 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 ~K~ be the total number of lines and ~t_i~ be the number of letters in line ~i~. Then a split is pretty if there exists ~k \in \{0, \ldots, K\}~ such that ~t_1 \ge \cdots \ge t_k~ and ~t_{k+1} \le \cdots \le t_K~.

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 ~1~ and no more than ~3000~ letters.

Subtask 1 [2/15]

~1 \le N \le 20~

Subtask 2 [3/15]

~1 \le N \le 100~

Subtask 3 [3/15]

~1 \le N \le 700~

Subtask 4 [6/15]

~1 \le N \le 5000~

Subtask 5 [1/15]

~1 \le N \le 30\,000~

Input Specification

The first line contains ~N~, the number of words in the phrase.
The second line contains ~N~ 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 Output

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.