#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cerr<<*i<<" "; cerr<<endl; }
inline bool valid(int x, int y, int W, int H){ return (x >= 0 && y >= 0 && x < W && y < H); }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

// Range Minimum Query
// class RMQは次の2つの処理をO(logn)で行う。
// 1. s, tが与えられた時、a[s], a[s + 1], ..., a[t - 1]の最小値を求める
// 2. i, xが与えられた時, a[i]の値をxに変更する。
// usage:
// int v = {5, 1, 3, 2, 6};
// vector<int> vv(v, v + 5);
// RMQ<int> rmq(vv);
// rmq.query_value(0, 5); -> 1 (半開区間で指定することに注意)
// rmq.update(1, 3); ({5, 1, 3, 2, 6} -> {5, 3, 3, 2, 6})
// rmq.query_value(0, 5); -> 2
// rmq.query_index(0, 5); -> 3 (a[3]が最小)
template <class T>
class RMQ{
  int N;
  vector<T> data;
  vector<int> segtree;
  bool compare(const T& a, const T& b){
    return a > b;
    // return a > b; // greater
    // return a.second <= b.second; // pair
    // return a.size() <= b.size() // string, array, ...
    // return abs(a) <= abs(b) // complex
  }
  int build(int idx, int left, int right){
    if(left + 1 == right){
      segtree[idx] = left;
    }else{
      const int mid = (left + right) / 2;
      int left_idx = build(idx * 2 + 1, left, mid);
      int right_idx = build(idx * 2 + 2, mid, right);
      if(compare(data[left_idx], data[right_idx])){
        segtree[idx] = left_idx;
      }else{
        segtree[idx] = right_idx;
      }
    }
    return segtree[idx];
  }
  int update_build(int k, int idx, int left, int right){
    if(!(left <= k && k < right)){
      //do nothing!
    } else if(left + 1 == right){
      segtree[idx] = left;
    }else{
      const int mid = (left + right) / 2;
      int left_idx = update_build(k, idx * 2 + 1, left, mid);
      int right_idx = update_build(k, idx * 2 + 2, mid, right);
      if(compare(data[left_idx], data[right_idx])){
        segtree[idx] = left_idx;
      }else{
        segtree[idx] = right_idx;
      }
    }
    return segtree[idx];
  }
public:
  RMQ(int N){
    data = vector<T>(N);
    this->N = data.size();
    segtree = vector<int>(4 * N, -1);
    build(0, 0, N);
  }
  RMQ(const vector<T>& v){
    data = vector<T>(v.begin(), v.end());
    N = data.size();
    segtree = vector<int>(4 * N, -1);
    build(0, 0, N);
  }

  T operator[](const int idx) const {
    return data[idx];
  }

  void update(int k, T a){
    data[k] = a;
    update_build(k, 0, 0, N);
  }

  inline int query_index(int left, int right) { return query_index(left, right, 0, 0, N); }
  int query_index(int left, int right, int i, int a, int b) {
    // [a, b) is the range of indexes[i]
    if (b <= left || right <= a) {
      // does not intersect
      return -1;
    } else if (left <= a && b <= right) {
      // contains
      return segtree[i];
    } else {
      const int m = (a+b)/2;
      const int l = query_index(left, right, 2*i+1, a, m);
      const int r = query_index(left, right, 2*i+2, m, b);
      if (l == -1) {
        return r;
      } else if (r == -1) {
        return l;
      } else {
        if(compare(data[l], data[r])){
          return l;
        } else {
          return r;
        }
      }
    }
  }
  inline T query_value(int left, int right) { return data[query_index(left, right)]; }

};
int main(){
  int N;
  cin>>N;
  vector<int> x(N);
  REP(i, N) cin >> x[i];
  int cur = 1;
  ll ans = (ll)N * (N + 1) / 2;
  RMQ<ll> rmq(N + 1);
  REP(i, N){
    rmq.update(x[i], rmq.query_value(0, x[i]) + x[i]);
  }
  ans -= rmq.query_value(0, N + 1);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 5216