#include<bits/stdc++.h> #define pii pair<int,int> #define fi first #define se second #define mk make_pair using namespace std; const int N=5e5+10,inf=1e9+10; void cmn(int &a,int b){if(b<a) a=b;} struct segtree{ int T[N<<3],tag[N<<3]; #define ls p*2 #define rs p*2+1 #define mid (l+r)/2 int Leaf[N<<1]; void pu(int p){ T[p]=min(T[ls],T[rs]); }void pd(int p){ cmn(tag[ls],tag[p]);cmn(tag[rs],tag[p]); cmn(T[ls],tag[p]);cmn(T[rs],tag[p]); tag[p]=inf; }void bd(int p,int l,int r){ T[p]=inf;tag[p]=inf; if(l==r){ Leaf[l]=p; return ; }bd(ls,l,mid);bd(rs,mid+1,r); }void asi(int p,int l,int r,int x,int v){ if(l==r){ T[p]=v;return ; }pd(p); if(x<=mid) asi(ls,l,mid,x,v); else asi(rs,mid+1,r,x,v);pu(p); }void chkmn(int p,int l,int r,int pl,int pr,int v){ if(pl>pr) return ; if(pl<=l&&r<=pr){ tag[p]=v;cmn(T[p],v); return ; }pd(p); if(pl<=mid) chkmn(ls,l,mid,pl,pr,v); if(pr>mid) chkmn(rs,mid+1,r,pl,pr,v); pu(p); }int qry(int p,int l,int r,int pl,int pr){ if(pl>pr) return inf; if(pl<=l&&r<=pr) return T[p]; int mn=inf;pd(p); if(pl<=mid) cmn(mn,qry(ls,l,mid,pl,pr)); if(pr>mid) cmn(mn,qry(rs,mid+1,r,pl,pr)); return mn; }void mdf(int p,int l,int r,int pl,int pr){ if(l==r){ cmn(T[Leaf[l]],T[Leaf[r+1]]-1); return ; }pd(p); if(pl<=mid) mdf(ls,l,mid,pl,pr); if(pr>mid) mdf(rs,mid+1,r,pl,pr); pu(p); } }sgt; int mv_tag=0,ad_tag=0,g=0; int n,m,a[N],b[N]; #define ALL 1,1,n+m+5 int main(){ cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=m;i++) cin>>b[i]; sort(b+1,b+m+1);b[0]=0,b[m+1]=inf-1; mv_tag=n+2;sgt.bd(ALL); set<pii> st; //for(int i=1;i<=m;i++) sgt.asi(ALL,i+mv_tag,0); for(int i=0;i<=m+1;i++) st.insert(mk(b[i],i)); for(int i=1;i<=n;i++){ int g0=g; int pos=(*(--st.lower_bound(mk(a[i],0)))).se; int pos2=(*(--st.upper_bound(mk(a[i],1e9)))).se; //cout<<pos2<<' '; g=inf;if(a[i]>=a[i-1]) g=g0; //cout<<sgt.qry(ALL,1+mv_tag,2+mv_tag)<<' '; cmn(g,sgt.qry(ALL,1+mv_tag,pos+mv_tag)+ad_tag); //update g sgt.asi(ALL,m+mv_tag,inf); //for(int j=1;j<=m;j++) cout<<sgt.qry(ALL,j+mv_tag,j+mv_tag)+ad_tag<<' '; //cout<<endl; mv_tag--;ad_tag++; //for(int j=1;j<=m;j++) cout<<sgt.qry(ALL,j+mv_tag,j+mv_tag)+ad_tag<<' '; //cout<<endl; if(b[pos+1]==a[i]) sgt.mdf(ALL,pos+1+mv_tag,pos2+mv_tag); //cout<<pos<<' '<<pos2<<endl; pos=(*(st.lower_bound(mk(a[i-1],1)))).se; //cout<<g<<endl; sgt.chkmn(ALL,pos+mv_tag,m+mv_tag,g0+1-ad_tag); //for(int j=1;j<=m;j++) cout<<sgt.qry(ALL,j+mv_tag,j+mv_tag)+ad_tag<<' '; //cout<<endl; } int ans=min(sgt.qry(ALL,1+mv_tag,m+mv_tag)+ad_tag,g); if(ans>m) cout<<-1<<endl; else cout<<ans<<endl; return 0; }