Interval Addition

Time limit4sMemory limit2048 MB

Summary

Given an array of up to 23 values, find the fewest operations that add a real number to a contiguous interval to make every element zero.

Level: Medium7 of 10
Topics: Bit manipulation, Dynamic programming, Prefix sum
Solved: No attempts yet

Problem

You are given an array $a$ of $n$ integers. You can perform operations on this array. In a single operation, you can add any real number $x$ to some consecutive interval of $a$ .

Determine the minimum number of operations that have to be performed to make all elements of $a$ equal to $0$ .

Input

The first line contains an integer $n$ ( $1 \leq n \leq 23$ ).

The second line contains the array $a_1, a_2, \ldots, a_n$ ( $0 \leq a_i \leq 10^9$ ).

Output

Print a line with a single integer: the minimum number of operations needed.

Examples2

Example 1
Input
```
5
1 2 3 2 1
```
Expected output
```
3
```
Example 2
Input
```
6
1 1 4 5 1 4
```
Expected output
```
4
```