Xoá sạch multiset

Cho một multiset chứa các số nguyên. Ban đầu, multiset có $a_1$ phần tử bằng $1$, $a_2$ phần tử bằng $2$, ..., $a_n$ phần tử bằng $n$.

Bạn có thể thực hiện hai loại thao tác:

1. Chọn hai số nguyên $l$ và $r$ ($l\le r$), sau đó xoá đúng một lần xuất hiện của $l$, một lần xuất hiện của $l+1$, ..., một lần xuất hiện của $r$ khỏi multiset. Thao tác này chỉ thực hiện được khi mỗi số từ $l$ đến $r$ đều xuất hiện ít nhất một lần.
2. Chọn hai số nguyên $i$ và $x$ ($x\ge 1$), sau đó xoá $x$ lần xuất hiện của $i$ khỏi multiset. Thao tác này chỉ thực hiện được khi multiset chứa ít nhất $x$ lần xuất hiện của $i$.

Hãy tìm số thao tác tối thiểu cần thực hiện để xoá hết mọi phần tử khỏi multiset.

Dữ liệu vào

• Dòng đầu chứa một số nguyên $n$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

• In ra một số nguyên — số thao tác tối thiểu cần thực hiện để xoá hết mọi phần tử khỏi multiset.

Ràng buộc

• $1\le n\le 5000$
• $0\le a_i\le {10}^9$

Ví dụ