Taro has decided to move. Taro has a lot of luggage, so I decided to ask a moving company to carry the luggage. Since there are various weights of luggage, I asked them to arrange them in order from the lightest one for easy understanding, but the mover left the luggage in a different order. So Taro tried to sort the luggage, but the luggage is heavy and requires physical strength to carry. Each piece of luggage can be carried from where it is now to any place you like, such as between other pieces of luggage or at the edge of the piece of luggage, but carrying one piece of luggage uses as much physical strength as the weight of that piece of luggage. Taro doesn't have much physical strength, so I decided to think of a way to arrange the luggage in order from the lightest one without using as much physical strength as possible.

Constraints

> 1 ≤ n ≤ 105
> 1 ≤ xi ≤ n (1 ≤ i ≤ n)
> xi ≠ xj (1 ≤ i, j ≤ n and i ≠ j)
>

* All inputs are given as integers

Input

> n
> x1 x2 ... xn
>

* n represents the number of luggage that Taro has
* x1 to xn represent the weight of each piece of luggage, and are currently arranged in the order of x1, x2, ..., xn.

Output

> S
>

* Output the total S of the minimum physical strength required to arrange the luggage in order from the lightest, but output the line break at the end

Examples

Input

4
1 4 2 3


Output

4


Input

5
1 5 3 2 4


Output

7


Input

7
1 2 3 4 5 6 7


Output

0


Input

8
6 2 1 3 8 5 4 7


Output

19
////////////////////////////////////////
///  tu3 pro-con template            ///
////////////////////////////////////////
#include <cassert>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <functional>
#include <vector>
#include <queue>
#include <string>
#include <complex>
#include <stack>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <regex>
using namespace std;

//// MACRO ////
#define countof(a) (sizeof(a)/sizeof(a[0]))

#define REP(i,n) for (int i = 0; i < (n); i++)
#define RREP(i,n) for (int i = (n)-1; i >= 0; i--)
#define FOR(i,s,n) for (int i = (s); i < (n); i++)
#define RFOR(i,s,n) for (int i = (n)-1; i >= (s); i--)
#define pos(c,i) c.being() + (i)
#define allof(c) c.begin(), c.end()
#define aallof(a) a, countof(a)
#define partof(c,i,n) c.begin() + (i), c.begin() + (i) + (n)
#define apartof(a,i,n) a + (i), a + (i) + (n)
#define long long long

#define EPS 1e-9
#define INF (1L << 30)
#define LINF (1LL << 60)

#define PREDICATE(t,a) [&](const t & a) -> bool
#define COMPARISON_T(t) bool(*)(const t &, const t &)
#define COMPARISON(t,a,b) [&](const t & a, const t & b) -> bool
#define CONVERTER(TSrc,t,TDest) [&](const TSrc &t)->TDest

//// i/o helper ////
struct _Reader { template <class T> _Reader operator ,(T &rhs) { cin >> rhs; return *this; } };
struct _Writer { bool f; _Writer() : f(false) { } template <class T> _Writer operator ,(const T &rhs) { cout << (f ? " " : "") << rhs; f = true; return *this; } };
#define READ(t,...) t __VA_ARGS__; _Reader(), __VA_ARGS__
#define WRITE(...) _Writer(), __VA_ARGS__; cout << endl

template <class T> struct vevector : public vector<vector<T>> { vevector(int n = 0, int m = 0, const T &initial = T()) : vector<vector<T>>(n, vector<T>(m, initial)) { } };
template <class T> struct vevevector : public vector<vevector<T>> { vevevector(int n = 0, int m = 0, int l = 0, const T &initial = T()) : vector<vevector<T>>(n, vevector<T>(m, l, initial)) { } };
template <class T> struct vevevevector : public vector<vevevector<T>> { vevevevector(int n = 0, int m = 0, int l = 0, int k = 0, const T &initial = T()) : vector<vevevector<T>>(n, vevevector<T>(m, l, k, initial)) { } };
template <class T> T read() { T t; cin >> t; return t; }
template <class T> vector<T> read(int n) { vector<T> v; REP(i, n) { v.push_back(read<T>()); } return v; }
template <class T> vevector<T> read(int n, int m) { vevector<T> v; REP(i, n) v.push_back(read<T>(m)); return v; }
template <class T> vevector<T> readjag() { return read<T>(read<int>()); }
template <class T> vevector<T> readjag(int n) { vevector<T> v; REP(i, n) v.push_back(readjag<T>()); return v; }

template <class T1, class T2> inline istream & operator >> (istream & in, pair<T1, T2> &p) { in >> p.first >> p.second; return in; }
template <class T1, class T2> inline ostream & operator << (ostream &out, pair<T1, T2> &p) { out << p.first << p.second; return out; }
template <class T> inline ostream & operator << (ostream &out, vector<T> &v)
{
	ostringstream ss;
	for (auto x : v) ss << x << ' ';
	auto s = ss.str();
	out << s.substr(0, s.length() - 1) << endl;
	return out;
}

//// start up ////
void solve();
int main()
{
	solve();
	return 0;
}

//// data structure ////

/// 2分セグメント木。RMQとかが解ける。
template<class T = int, class TParentFunc = const T& (*)(const T&, const T&)>
struct SegTree
{
	unsigned msb(unsigned v) { v |= v >> 1; v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16; return (v >> 1) + 1; }

	int size;
	vector<T> tree;
	TParentFunc parent;

	SegTree(int count, TParentFunc parentBuilder = std::min, T initialFill = INF)
		: size(msb(count - 1) << 1)
		, tree(size * 2)
		, parent(parentBuilder)
	{
		fill(partof(tree, size, size), initialFill);
		rebuild();
	}

	// []を使うと更新されないのでrebuildすること。数が少なければupdateの方がよい。
	T& operator[](int i) { return tree[i + size]; }
	void rebuild() { RREP(i, size) { tree[i] = parent(tree[i * 2], tree[i * 2 + 1]); } }

	void update(int index, T value)
	{
		tree[index + size] = value;
		for (int i = (index + size) / 2; i > 0; i /= 2)
			tree[i] = parent(tree[i * 2], tree[i * 2 + 1]);
	}

	T query(int s, int e, int i, int l, int r, T value)
	{
		if (r <= s || e <= l) return value;
		if (s <= l && r <= e) return parent(value, tree[i]);
		value = query(s, e, i * 2, l, (l + r) / 2, value);
		value = query(s, e, i * 2 + 1, (l + r) / 2, r, value);
		return value;
	}

	T query(int start, int count, T initialValue)
	{
		return query(start, start + count, 1, 0, size, initialValue);
	}
};


////////////////////
/// template end ///
////////////////////

void solve()
{
	int testcases = 1;
	REP(testcase, testcases)
	{
		READ(int, N);
		auto x = read<int>(N);
		SegTree<long> st(N, max, 0);
		REP(i, N) st.update(x[i] - 1, st.query(0, x[i] - 1, 0) + x[i]);
		WRITE(accumulate(allof(x), 0LL) - st.query(0, N, 0));
	}
}