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
#include <bits/stdc++.h>

typedef long long ll;
#define int ll

#define range(i, a, n) for(int (i) = (a); (i) < (n); (i)++)
#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
using namespace std;

// -----------------------
namespace SegmentTrees{
    template<typename T>
    class RMQ{
    private:
        int Pow2Fit(int _n){
            int d = 1;
            while((d << 1) <= _n) d <<= 1;
            return d;
        }

    public:
        vector<T> dat;
        int n, size;

        RMQ(int _n){
            n = Pow2Fit(_n) << 1;
            size = 2 * n - 1;
            dat = vector<T>(size, 0);
        }

        // node v := a (0-indexed)
        void set(int v, T a){

            // leaf
            v += n - 1;
            dat[v]=a;

            // update toward root
            while(v > 0){
                int parent = v = (v - 1) / 2;
                int chl = parent * 2 + 1, chr = parent * 2 + 2;
                dat[parent] = max(dat[chl], dat[chr]);
            }
        }

        T get(int v){ // v (0-indexed)
            return dat[v + n - 1];
        }

        T query(int a, int b){ // [a,b)
            return query(0, a, b, 0, n);
        }

    private:
        T query(int v, int a, int b, int l, int r){ // [a,b)
            if(r <= a || b <= l) return 0; // out range
            if(a <= l && r <= b) return dat[v]; // covered
 
            T vl = query(v * 2 + 1, a, b, l, (l + r) / 2),
              vr = query(v * 2 + 2, a, b, (l + r) / 2, r);

            return max(vl, vr);
        }
    };
}

using namespace SegmentTrees;
// -----------------------

signed main(){
    int n; cin >> n;
    RMQ<int> rmq(n);

    rep(i, n){
        int x; cin >> x;
        rmq.set(x - 1, rmq.query(0, x) + x);
    }

    cout << n * (n + 1) / 2 - rmq.query(0, n) << endl;
}