Interval Addition

시간 제한4초메모리 제한2048 MB

요약

수열이 주어질 때, 연속한 구간에 실수를 더하는 연산만으로 모든 원소를 0으로 만드는 최소 연산 횟수를 구한다.

난이도: 어려움10점 중 9점
유형: 동적 계획법, 그리디, 백트래킹, 비트 연산
정답자: 아직 제출이 없습니다

문제

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$ .

입력

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$ ).

출력

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

예제2

예제 1
입력
```
5
1 2 3 2 1
```
예상 출력
```
3
```
예제 2
입력
```
6
1 1 4 5 1 4
```
예상 출력
```
4
```