#include <bits/stdc++.h>
template <typename T>
class SegmentTreeUpdMax {
    int n;
    const T inf_min = std::numeric_limits<T>::min();
    std::vector<T> node;
public:
    SegmentTreeUpdMax(std::vector<T> v) {
        int sz = v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n, inf_min);
        for(int i=0;i<sz;++i) node[i+n-1] = v[i];
        for(int i=n-2;i>=0;--i) node[i] = std::max(node[2*i+1], node[2*i+2]);
    }
    void update(int idx, T val) {
        assert(0 <= idx && idx < n);
        node[idx + n - 1] = val;
        idx = idx + n - 1;
        while(idx > 0) {
            idx = (idx - 1) / 2;
            node[idx] = std::max(node[2*idx + 1], node[2 * idx + 2]);
        }
    }
    T query(int a, int b, int k, int l, int r) {
        if(r <= a || b <= l) return inf_min;
        if(a <= l && r <= b) return node[k];
        T vl = query(a, b, k*2+1, l, ((l+r)/2));
        T vr = query(a, b, k*2+2, (l+r)/2, r);
        return std::max(vl, vr);
    }
    T query(int a, int b) {
        return query(a, b, 0, 0, n);
    }
};
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const ll MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;
template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}
template<typename T1, typename T2>
ostream& operator<<(ostream &os, const pair<T1, T2> p) {
  os << p.first << ":" << p.second;
  return os;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  ll n; cin >> n;
  vll x(n);
  for(int i=0;i<n;++i) {
    cin >> x[i];
  }
  vll node(n+1);
  SegmentTreeUpdMax<ll> st(node);
  for(int i=0;i<n;++i) {
    ll tmp = x[i] + st.query(0, x[i]);
    st.update(x[i], tmp);
  }
  ll mi = LINF;
  for(int i=1;i<=n+1;++i) {
    mi = min(mi, (ll)(n * (n + 1) / 2 - st.query(0, i)));
  }
  cout << mi << endl;
}

