구간 편집

스프레드시트에 셀이 한 줄로 놓여 있다. 처음에는 모든 셀이 비어 있다. 다음 두 가지 연산을 수행할 수 있다.

1. 연속된 구간의 셀을 원하는 양의 정수 하나로 바꾼다. 구간의 모든 셀은 연산 후 같은 값을 가진다.
2. 연속된 구간의 셀 값을 지운다. 구간의 모든 셀은 연산 후 비게 된다.

원하는 최종 셀 값이 주어졌을 때, 그 값을 얻는 데 필요한 편집 연산의 최소 횟수를 구하시오.

첫째 줄에 셀의 개수를 나타내는 정수 $n$ ($1 \leq n \leq 800$)이 주어진다. 셀은 1번부터 $n$번까지 번호가 매겨져 있다.

이어지는 $n$개의 줄에는 $0$ 이상 $10^9$ 이하의 정수가 한 개씩 주어진다. $i$번째 줄의 정수가 $0$이면 모든 연산 후 $i$번 셀이 비어 있어야 한다. 그렇지 않으면 그 값이 $i$번 셀의 최종 값이다.

필요한 편집 연산의 최소 횟수를 한 줄에 출력한다.