# Clear the Multiset

## 题目描述

You have a multiset containing several integers. Initially, it contains \$ a_1 \$ elements equal to \$ 1 \$ , \$ a_2 \$ elements equal to \$ 2 \$ , ..., \$ a_n \$ elements equal to \$ n \$ . You may apply two types of operations: - choose two integers \$ l \$ and \$ r \$ ( \$ l \le r \$ ), then remove one occurrence of \$ l \$ , one occurrence of \$ l + 1 \$ , ..., one occurrence of \$ r \$ from the multiset. This operation can be applied only if each number from \$ l \$ to \$ r \$ occurs at least once in the multiset; - choose two integers \$ i \$ and \$ x \$ ( \$ x \ge 1 \$ ), then remove \$ x \$ occurrences of \$ i \$ from the multiset. This operation can be applied only if the multiset contains at least \$ x \$ occurrences of \$ i \$ . What is the minimum number of operations required to delete all elements from the multiset?

## 输入输出格式

### 输入格式

The first line contains one integer \$ n \$ ( \$ 1 \le n \le 5000 \$ ). The second line contains \$ n \$ integers \$ a_1 \$ , \$ a_2 \$ , ..., \$ a_n \$ ( \$ 0 \le a_i \le 10^9 \$ ).

### 输出格式

Print one integer — the minimum number of operations required to delete all elements from the multiset.

4
1 4 1 1

2

5
1 0 1 0 1

3