Cho một tập hợp gồm \(a_i\) số \(i\) \((1 \leq i \leq n)\). Bạn có thể sử dụng hai thao tác sau:

• Chọn hai số nguyên \(l\) và \(r\) \((l \leq r)\), sau đó xoá số \(l\) đúng \(1\) lần, số \(l + 1\) đúng \(1\) lần, ... và số \(r\) đúng \(1\) lần khỏi tập hợp.
• Chọn hai số nguyên \(i\) và \(x\) \((x \geq 1)\), sau đó xoá số \(x\) đúng \(i\) lần khỏi tập hợp.

Hãy tìm số thao tác ít nhất cần dùng để xoá hết số khỏi tập hợp.

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \leq n \leq 5000)\).
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((0 \leq a_i \leq 10^9)\).

Output

• Một số nguyên duy nhất là số thao tác ít nhất cần dùng để xoá hết số khỏi tập hợp.

Example

4
1 4 1 1

2