Problem Description

Aoki, an employee of Mixi, has a sequence $ A $ consisting of $ N $ elements, initially all elements are $ 0 $.

Aoki wants to repeat the following operation $ 0 $ or more times to make the $ i $-th element of the sequence equal to $ a_i $ for all $1 \leq i \leq N$.

• Decide on positive integers $ k, l $ that satisfy $1 \leq k \leq N$ and $1 \leq l \leq N+1-k$. Choose a non-negative integer sequence $(0 \leq ) B_1 \leq B_2 \leq ... \leq B_k$ as you like, and for each $1 \leq i \leq k$, set $ A_{l+i-1} := A_{l+i-1} + B_i $.

Each operation can use different $ k, l, B $. Find the minimum number of operations required for Aoki to achieve the desired sequence.

Input Format

The input is given from the standard input in the following format:

$ N $ $ a_1 $ $ a_2 $ $ ... $ $ a_N $

Output Format

Output the minimum number of operations required for Aoki to achieve the desired sequence.

Sample Input and Output

Sample Input #1

2
3 4

Sample Output #1

1

Sample Input #2

2
4 3

Sample Output #2

2

Sample Input #3

4
4 0 4 0

Sample Output #3

2

Notes/Hints

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $0 \leq a_i \leq 10^9$
• All inputs are integers

Sample Explanation 1

By setting $k = 2, l = 1, B = \{3, 4\}$, Aoki can achieve the desired sequence with 1 operation.

Sample Explanation 2

In the first operation, set $k = 2, l = 1, B = \{3, 3\}$, then $ A $ becomes $\{3, 3\}$. In the second operation, set $k = 1, l = 1, B = \{1\}$, then $ A $ becomes $\{4, 3\}$. Therefore, Aoki can achieve the desired sequence with 2 operations, and it is not possible to achieve it with fewer than 2 operations, so output $ 2 $.

见题面 Input 部分

见题面 Output 部分