60045 조약돌 Gold III

문제

일렬로 놓인 N개의 위치에 조약돌이 있다. 두 가지 연산이 가능하다:

1. 인접한 두 위치에서 같은 개수의 조약돌을 동시에 제거
2. 한 위치에서 임의 개수의 조약돌 제거

모든 조약돌을 제거하는 최소 연산 횟수를 구하시오.

입력

첫째 줄에 N (2 ≤ N ≤ 2,500)이 주어진다. 둘째 줄에 각 위치의 조약돌 수가 주어진다. (1 ≤ 조약돌 ≤ 10^8)

출력

최소 연산 횟수.