E. Non-decreasing Sequence
time limit per test
1.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a sequence of $$$n$$$ integers $$$a_1, a_2, \ldots a_n$$$.

In one operation you can do the following:

  • Select an index $$$i$$$ such that $$$1 \le i \lt n$$$.
  • Merge the two adjacent elements $$$a_i$$$ and $$$a_{i + 1}$$$ by their sum.

For example, if $$$a = [2, 3, 7, 4, 5]$$$ and you select $$$i = 3$$$, then after performing the operation, the array will be $$$[2, 3, \underline{7}, \underline{4}, 5] \rightarrow [2, 3, 7 + 4, 5] \rightarrow [2, 3, 11, 5]$$$.

Find the minimum number of operations to make the array non-decreasing.

Input

The first line contains an integer $$$n$$$ $$$(1\le n \le 3000)$$$  — the length of the array.

The second line contains $$$n$$$ space-separated integers $$$a_1,a_2,...,a_n$$$ $$$(1\le a_i \le 10^{15})$$$

Output

Output an integer  — the minimum number of operations needed to make the array non-decreasing.

Examples
Input
6
4 3 2 7 6 9
Output
2
Input
7
55 50 87 17 36 90 6
Output
4
Input
17
55 50 87 17 36 90 6 74 67 92 40 18 97 78 86 41 88
Output
10
Note

In the first testcase, one possible optimal sequence of operations would be: $$$[4,\underline{3},\underline{2},7,6,9] \rightarrow [4,5,7,\underline{6},\underline{9}] \rightarrow [4,5,7,15] $$$. It can shown that you can't make the array non-decreasing in less than $$$2$$$ operations.

In the second testcase, an optimal sequence of operations would be: $$$[55,\underline{50},\underline{87},17,36,90,6] \rightarrow [55,137,\underline{17},\underline{36},90,6]$$$ $$$\rightarrow [55,137,53,\underline{90},\underline{6}] \rightarrow [55,137,\underline{53},\underline{96}] \rightarrow [55,137,149] $$$.