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 ≤ 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 ≥ 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 ≤ n ≤ 5000).

The second line contains n integers a_1, a_2, ..., a_n (0 ≤ a_i ≤ 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
#include <bits/stdc++.h>
using std::cin, std::cout, std::bitset, std::complex;
using std::min_element, std::max_element, std::accumulate;
using std::priority_queue, std::set, std::map, std::unordered_map;
using std::sort, std::min, std::max, std::reverse;
using std::vector, std::array, std::string, std::pair, std::list, std::queue;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using ull = unsigned long long int;
using ll = long long int;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vd = vector<double>;
using vvd = vector<vd>;
using vvvd = vector<vvd>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using cdouble = complex<double>;
const double eps = 1e-7;
bool feq(double x, double y) { return abs(x - y) <= eps; }
bool inrange(ll x, ll t) { return x >= 0 && x < t; }
bool inrange(vll xs, ll t) {
  for (const auto &x : xs)
    if (!(x >= 0 && x < t)) return false;
  return true;
}
int ceillog2(ll x) {
  int m = int(log2(x));
  return m + ((1LL << m) < x ? 1 : 0);
}
int floorlog2(ll x) {
  int m = int(log2(x));
  return m - ((1LL << m) > x ? 1 : 0);
}
const string endl = "\n";
template <class T>
T reversed(T container) {
  reverse(container.begin(), container.end());
  return container;
}
template <class T>
void printv(const vector<T> &v) {
  for (const T &x : v) cout << x << " ";
  cout << endl;
}
template <class T>
void printmx(const vector<vector<T>> &mx) {
  for (const vector<T> &v : mx) printv(v);
}
ll rndf(double x) { return (ll)(x + (x >= 0 ? 0.5 : -0.5)); }
ll floorsqrt(ll x) {
  ll m = (ll)sqrt((double)x);
  return m + (m * m <= x ? 0 : -1);
}
ll ceilsqrt(ll x) {
  ll m = (ll)sqrt((double)x);
  return m + (x <= m * m ? 0 : 1);
}
ll rnddiv(ll a, ll b) { return (a / b + (a % b * 2 >= b ? 1 : 0)); }
ll ceildiv(ll a, ll b) { return (a / b + (a % b == 0 ? 0 : 1)); }
ll gcd(ll m, ll n) {
  if (n == 0)
    return m;
  else
    return gcd(n, m % n);
}
ll lcm(ll m, ll n) { return ll(m) * ll(n) / gcd(m, n); }
int solve(int l, int r, int d, const vi &a) {
  if (r - l == 0) return 0;
  int m = *(std::min_element(a.begin() + l, a.begin() + r));
  int diff = m - d;
  if (r - l <= diff)
    return r - l;
  else {
    int ret = diff;
    int s = l;
    for (int i = l; i <= r; ++i) {
      if (i == r || a[i] == m) {
        ret += solve(s, i, d + diff, a);
        if (r - l <= ret) return r - l;
        s = i + 1;
      }
    }
    return ret;
  }
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  ;
  int n;
  cin >> n;
  vi a(n);
  for (int i = 0; i < int(n); i++) cin >> a[i];
  int s = 0;
  int ans = solve(0, n, 0, a);
  cout << ans << endl;
}
