#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> P;

typedef long long ll;

#define INF 1000000000000LL

ll max(ll a, ll b) { return a > b ? a : b; }

struct Bit {
	int bitSize;
	vector<ll> bit;
	void init(int n, ll v) {
		bitSize = n;
		bit = vector<ll>(n+1, 0);
	}
	void add(int n, ll v) {
		++n;
		while (n <= bitSize) {
			bit[n] = max(bit[n], v);
			n += n & -n;
		}
	}
	ll sum(int r) {
		ll ret = 0;

		while (r) {
			ret = max(ret, bit[r]);
			r -= r & -r;
		}

		return ret;
	}
};

Bit bit;

int main() {
	int N; cin >> N;
	vector<P> v;
	for (int i = 0; i < N; ++i) {
		int x; cin >> x;
		v.push_back( P(x, i) );
	}

	sort( v.begin(), v.end() );

	ll sum = (ll)N*(N+1)/2;

	bit.init(N, 0);
	ll ans = 0;
	for (int i = 0; i < N; ++i) {
		ll val = bit.sum(v[i].second+1) + v[i].first;
		ans = max(ans, val);
		bit.add(v[i].second, val);
//		cout << bit.sum(v[i].second+1) << endl;
	}
	ans = sum-ans;
	cout << ans << endl;
}