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 namespace std;
struct fast_ios {
  fast_ios() {
    cin.tie(nullptr), ios::sync_with_stdio(false),
        cout << fixed << setprecision(20);
  };
} fast_ios_;
template <class T>
auto add = [](T a, T b) -> T { return a + b; };
template <class T>
auto f_max = [](T a, T b) -> T { return max(a, b); };
template <class T>
auto f_min = [](T a, T b) -> T { return min(a, b); };
template <class T>
using V = vector<T>;
using Vl = V<int>;
using VVl = V<Vl>;
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  for (int i = 0; i < (int)v.size(); i++)
    os << v[i] << (i + 1 != v.size() ? " " : "");
  return os;
}
template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& in : v) is >> in;
  return is;
}
template <class T>
bool chmax(T& a, const T& b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
int gcd(int a, int b) {
  if (b == 0)
    return a;
  else
    return gcd(b, a % b);
}
int ceil(int a, int b) { return (a + b - 1) / b; }
int digit(int a) { return (int)log10(a); }
int e_dist(pair<int, int> a, pair<int, int> b) {
  return abs(a.first - b.first) * abs(a.first - b.first) +
         abs(a.second - b.second) * abs(a.second - b.second);
}
int m_dist(pair<int, int> a, pair<int, int> b) {
  return abs(a.first - b.first) + abs(a.second - b.second);
}
bool check_overflow(int a, int b, int limit) { return a > limit / b; }
void Worshall_Floyd(VVl& g) {
  for (int k = (0), k_end_ = (((int)(g).size())); k < k_end_; ++k)
    for (int i = (0), i_end_ = (((int)(g).size())); i < i_end_; ++i)
      for (int j = (0), j_end_ = (((int)(g).size())); j < j_end_; ++j)
        chmin(g[i][j], g[i][k] + g[k][j]);
}
const int MOD1000000007 = 1000000007, MOD998244353 = 998244353, INF = 5e12;
int dx[8] = {1, 0, -1, 0, 1, -1, 1, -1}, dy[8] = {0, 1, 0, -1, -1, -1, 1, 1};
bool YN(bool flag) {
  cout << (flag ? "YES" : "NO") << '\n';
  return flag;
}
bool yn(bool flag) {
  cout << (flag ? "Yes" : "No") << '\n';
  return flag;
}
struct Edge {
  int from, to;
  int cost;
  Edge() {}
  Edge(int u, int v, int c) {
    cost = c;
    from = u;
    to = v;
  }
  bool operator<(const Edge& e) const { return cost < e.cost; }
};
struct WeightedEdge {
  int to;
  int cost;
  WeightedEdge(int v, int c = 1) {
    to = v;
    cost = c;
  }
  bool operator<(const WeightedEdge& e) const { return cost < e.cost; }
};
using WeightedGraph = V<V<WeightedEdge>>;
int N;
int main() {
  cin >> N;
  Vl arr(N);
  set<int> xs;
  xs.insert(0);
  cin >> arr;
  for (int i = (0), i_end_ = (N); i < i_end_; ++i) {
    xs.insert(arr[i]);
  }
  map<int, int> fx;
  Vl vals;
  int idx = 0;
  for (int v : xs) fx[v] = idx, vals.push_back(v), idx++;
  for (int i = (0), i_end_ = (N); i < i_end_; ++i) arr[i] = fx[arr[i]];
  VVl dp(N + 1, Vl(idx, N));
  dp[0][0] = 0;
  for (int i = (0), i_end_ = (N); i < i_end_; ++i) {
    for (int j = (0), j_end_ = (idx); j < j_end_; ++j) {
      if (arr[i] > j) {
        chmin(dp[i + 1][arr[i]], dp[i][j] + vals[arr[i]] - vals[j]);
        chmin(dp[i + 1][j], dp[i][j] + 1);
      } else
        chmin(dp[i + 1][arr[i]], dp[i][j]);
    }
  }
  cout << *min_element((dp[N]).begin(), (dp[N]).end()) << '\n';
}
