Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

divide and conquer

dp

greedy

*2200

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Clear the Multiset

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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?

Input

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$$$).

Output

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

Examples

Input

4 1 4 1 1

Output

2

Input

5 1 0 1 0 1

Output

3

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/23/2024 07:08:53 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|