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 <cstdio>
#include <iostream>
#include <vector>
#include <list>
#include <cmath>
#include <fstream>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <complex>
#include <iterator>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <stack>
#include <climits>
#include <deque>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
double EPS=1e-10;
double EQ(double a,double b){
    return abs(a-b)<EPS;
}
void fast_stream(){
  std::ios_base::sync_with_stdio(0);
}
template<class T>
string IntToString(T num){
  string res;stringstream ss;ss<<num;
  return ss.str();
}
ll StringToInt(string &str){
  ll res=0;
  for(int i=0;i<(int)str.size();i++)
    res=(res*10+str[i]-'0');
  return res;
}
const int MAX_N=1<<20;
const ll INF=1LL<<50;
class RMQ{
public:
  // セグメント木を持つグローバル配列
  int n;
  ll dat[2*MAX_N-1];
  // 初期化
  void init(int n_){
    n=1;
    while(n<n_)n*=2;
    fill(dat,dat+2*n-1,0);
  }
  // k番目の値(0-indexed)をaに変更
  void update(int k,ll a){
    // 葉の節点
    k+=n-1;
    dat[k]=a;
    // のぼりながら更新
    while(k>0){
      k=(k-1)/2;
      dat[k]=max(dat[k*2+1],dat[k*2+2]);
    }
  }
  // [a,b)の最大値を求める
  // kは節点の番号、l,rはその節点が[l,r)に対応づいていることを表す
  // したがって、外からはquery(a,b,0,0,n)として呼ぶ
  ll _query(int a,int b,int k,int l,int r){
    if(r<=a||b<=l)return 0;
    else if(a<=l&&r<=b)return dat[k];
    ll vl=_query(a,b,k*2+1,l,(l+r)/2);
    ll vr=_query(a,b,k*2+2,(l+r)/2,r);
    return max(vl,vr);
  }
  ll query(int a,int b){
    return _query(a,b,0,0,n);	
  }
};
int as[1000001];
ll dp[100001];
ll sum;
RMQ rmq;
int main(){
  int n;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>as[i];
    sum+=as[i];
  }
  rmq.init(n+1);
  rmq.update(as[0],as[0]);
  ll res=as[0];
  for(int i=1;i<n;i++){
    ll val=rmq.query(0,as[i]);
    rmq.update(as[i],val+as[i]);
    res=max(res,val+as[i]);
  }
  cout<<sum-res<<endl;
  return 0;
}