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>
                                        #include<iostream>
                                        #include<cstdio>
                                        #include<vector>
                                        #include<queue>
                                        #include<map>
                                        #include<cstring>
                                        #include<string>
                                        #include <math.h>
                                        #include<algorithm>
                                    //    #include <boost/multiprecision/cpp_int.hpp>
                                        #include<functional>
                                #define int long long
                                        #define inf  1000000007
                                        #define pa pair<int,int>
                                        #define ll long long
                                        #define pal pair<double,int>
                                        #define ppa pair<int,int>
                                        #define ppap pair<int,pa>
                                        #define ssa pair<string,int>
                                        #define  mp make_pair
                                        #define  pb push_back
                                        #define EPS (1e-12)
                                        #define equals(a,b) (fabs((a)-(b))<EPS)
                                  #define VI vector<int>
                                        using namespace std;
                                        
                                  class pas{
                                    	public:
                                    	int x,y;
                                    	pas(int x=0,int y=0):x(x),y(y) {}
                                    	pas operator + (pas p) {return pas(x+p.x,y+p.y);}
                                    	pas operator - (pas p) {return pas(x-p.x,y-p.y);}
                                    	pas operator * (int a) {return pas(x*a,y*a);}
                                    	pas operator / (int a) {return pas(x/a,y/a);}
                                    //	double absv() {return sqrt(norm());}
                                    	int norm() {return x*x+y*y;}
                                    	bool operator < (const pas &p) const{
                                   		return x != p.x ? x<p.x: y<p.y;
                                   	}
                                  //		bool operator < (const pas &p) const{
                                    //		return y != p.y ? y<p.y: x<p.x;
                                    //	}
                                    	bool operator == (const pas &p) const{
                                    		return x==p.x && y==p.y;
                                    	}
                                    };

                                        class Point{
                                        	public:
                                        	double x,y;
                                        	Point(double x=0,double y=0):x(x),y(y) {}
                                        	Point operator + (Point p) {return Point(x+p.x,y+p.y);}
                                        	Point operator - (Point p) {return Point(x-p.x,y-p.y);}
                                        	Point operator * (double a) {return Point(x*a,y*a);}
                                        	Point operator / (double a) {return Point(x/a,y/a);}
                                        	double absv() {return sqrt(norm());}
                                        	double norm() {return x*x+y*y;}
                                        	bool operator < (const Point &p) const{
                                        		return x != p.x ? x<p.x: y<p.y;
                                        	}
                                        	bool operator == (const Point &p) const{
                                        		return fabs(x-p.x)<EPS && fabs(y-p.y)<EPS;
                                        	}
                                        };
                                        typedef Point Vector;
                                 #define pl pair<int,pas>
                                        struct Segment{
                                        Point p1,p2;
                                        };
                                         double dot(Vector a,Vector b){
                                        	return a.x*b.x+a.y*b.y;
                                        }
                                        double cross(Vector a,Vector b){
                                        	return a.x*b.y-a.y*b.x;
                                        }
                                    
            bool parareru(Point a,Point b,Point c,Point d){
            //	if(abs(cross(a-b,d-c))<EPS)cout<<"dd "<<cross(a-b,d-c)<<endl;
            	return abs(cross(a-b,d-c))<EPS;
            }
            double distance_ls_p(Point a, Point b, Point c) {
              if ( dot(b-a, c-a) < EPS ) return (c-a).absv();
              if ( dot(a-b, c-b) < EPS ) return (c-b).absv();
              return abs(cross(b-a, c-a)) / (b-a).absv();
            }
            bool is_intersected_ls(Segment a,Segment b) {
            	if(a.p1==b.p1||a.p2==b.p1||a.p1==b.p2||a.p2==b.p2) return false;
            	if(parareru((a.p2),(a.p1),(a.p1),(b.p2))&&parareru((a.p2),(a.p1),(a.p1),(b.p1))){
            //		cout<<"sss"<<endl;
            		if(dot(a.p1-b.p1,a.p1-b.p2)<EPS) return true;
            		if(dot(a.p2-b.p1,a.p2-b.p2)<EPS) return true;
            		if(dot(a.p1-b.p1,a.p2-b.p1)<EPS) return true;
            		if(dot(a.p1-b.p2,a.p2-b.p2)<EPS) return true;
            		return false;
            	}
              else return ( cross(a.p2-a.p1, b.p1-a.p1) * cross(a.p2-a.p1, b.p2-a.p1) < EPS ) && ( cross(b.p2-b.p1, a.p1-b.p1) * cross(b.p2-b.p1, a.p2-b.p1) < EPS );
            }
            double segment_len(Segment a){
            	
            	return (a.p1-a.p2).absv();
            }
            double segment_dis(Segment a,Segment b){
            	if(is_intersected_ls(a,b))return 0;
            	double r=distance_ls_p(a.p1, a.p2, b.p1);
            	r=min(r,distance_ls_p(a.p1, a.p2, b.p2));
            	r=min(r,distance_ls_p(b.p1, b.p2, a.p2));
            	r=min(r,distance_ls_p(b.p1, b.p2, a.p1));
            	return r;
            }
            Point intersection_ls(Segment a, Segment b) {
              Point ba = b.p2-b.p1;
              double d1 = abs(cross(ba, a.p1-b.p1));
              double d2 = abs(cross(ba, a.p2-b.p1));
              double t = d1 / (d1 + d2);
             
              return a.p1 + (a.p2-a.p1) * t;
            }
			pair<Point,Point> circle_intersection(Point c1,double r1,Point c2,double r2){
				double d=(c1-c2).absv();
				double h=(r1*r1-r2*r2+d*d)/2.0/d;
				double l=sqrt(r1*r1-h*h);
			//	cout<<d<<" "<<h<<" "<<l<<endl;
				Point asi=c1+(c2-c1)*h/((c2-c1).absv());
				Vector r1r2=(c2-c1)/((c2-c1).absv());
				Vector sui={r1r2.y,-r1r2.x};
			//	cout<<sui.x<<" "<<sui.y<<endl;
				pair<Point,Point> z=mp(asi+sui*l,asi-sui*l);
				if(z.first.x>z.second.x) swap(z.first,z.second);
				return z;
			}
int N=262144;
pa sgt[530000];

pa minis(int i,int j ){
if(i==j) return sgt[i];
	else if(i%2==1){
		pa z=minis(i+1,j);
		if(sgt[i].first>z.first)return sgt[i] ;
		else return z;
	}
		else if(j%2==0) 	{
		pa z=minis(i,j-1);
		if(sgt[j].first>z.first)return sgt[j] ;
		else return z;
	}
else return minis(i/2,j/2);
}

pa sgtmin(int i ,int j) {
	return minis(i+N,j+N);
}

void upd(int x,int y){
	x+=N;
sgt[x].first=y;
	sgt[x].second=x;
x=x/2;
while(x != 0){
	if(sgt[2*x+1].first>sgt[2*x].first){
		sgt[x]=sgt[2*x+1];
	}
	else sgt[x]=sgt[2*x];

x=x/2;
}
}


         signed main(){
int n;
     
      for(int i=N;i<2*N;i++) sgt[i]=make_pair(0,i-N);
         	cin>>n;
         	for(int i=N-1;i>0;i--){
		if(sgt[2*i].first<sgt[2*i+1].first) sgt[i]=sgt[2*i+1];
		else sgt[i]=sgt[2*i];
	}
         	for(int i=1;i<=n;i++){
         		int t;
         		cin>>t;
         		
         		int e=sgtmin(0,t-1).first;
         		upd(t,e+t);
         	}
         	int ans=0;
         	for(int i=1;i<=n;i++)ans=max(ans,sgt[N+i].first);
         	cout<<n*(n+1)/2-ans<<endl;
           	return 0;
           }
