#include<bits/stdc++.h> using namespace std; #define lson (pos<<1) #define rson (pos<<1|1) int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;} const int MAXN=1000030,inf=1e9; void Min(int &x,int y){x=min(x,y);} int n,m,a[MAXN],b[MAXN],f[MAXN],g[MAXN],p[MAXN],ct; struct segtree{ int tot,cnt; int t[MAXN<<2],lz[MAXN<<2]; void pushup(int pos){ t[pos]=min(t[lson],t[rson]); } void upd(int pos,int x){ Min(t[pos],x),Min(lz[pos],x); } void pushdown(int pos){ if(lz[pos]<inf)upd(lson,lz[pos]),upd(rson,lz[pos]),lz[pos]=inf; } void build(int pos,int l,int r){ t[pos]=lz[pos]=inf; if(l==r)return; int mid=(l+r)>>1; build(lson,l,mid);build(rson,mid+1,r); } void update(int pos,int l,int r,int ql,int qr,int x){ if(ql<=l&&qr>=r){ upd(pos,x); return; } int mid=(l+r)>>1;pushdown(pos); if(ql<=mid)update(lson,l,mid,ql,qr,x); if(qr>mid)update(rson,mid+1,r,ql,qr,x); pushup(pos); } int query(int pos,int l,int r,int ql,int qr){ if(ql<=l&&qr>=r)return t[pos]; int mid=(l+r)>>1;pushdown(pos); if(qr<=mid)return query(lson,l,mid,ql,qr); if(ql>mid)return query(rson,mid+1,r,ql,qr); return min(query(lson,l,mid,ql,qr),query(rson,mid+1,r,ql,qr)); } void update1(int pos,int l,int r,int ql,int qr){ if(l==r){ p[++ct]=t[pos]+cnt; return; } pushdown(pos); int mid=(l+r)>>1; if(ql<=mid)update1(lson,l,mid,ql,qr); if(qr>mid)update1(rson,mid+1,r,ql,qr); } void update2(int pos,int l,int r,int ql,int qr){ if(l==r){ Min(t[pos],p[++ct]-cnt); return; } pushdown(pos); int mid=(l+r)>>1; if(ql<=mid)update2(lson,l,mid,ql,qr); if(qr>mid)update2(rson,mid+1,r,ql,qr); pushup(pos); } void init(){tot=n+1,cnt=0;build(1,1,n+m+5);} void add(){ // cout<<"add"<<endl; tot--,cnt++;} void update(int l,int r,int x){ // cout<<"upd "<<l<<" "<<r<<" "<<x<<endl; if(l<=r)update(1,1,n+m+5,l+tot,r+tot,x-cnt); } int query(int l,int r){ // cout<<"Q"<<" "<<l<<" "<<r<<endl; return l>r?0:query(1,1,n+m+5,l+tot,r+tot)+cnt; } void update1(int l,int r){ // cout<<"ud1"<<" "<<l<<" "<<r<<endl; if(l<=r)update1(1,1,n+m+5,l+tot,r+tot);ct=0; } void update2(int l,int r){ // cout<<"ud2"<<" "<<l<<" "<<r<<endl; if(l<=r)update2(1,1,n+m+5,l+tot,r+tot);ct=0; } }T; void slv(){ n=read(),m=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=m;i++)b[i]=read(); sort(b+1,b+m+1); T.init(); T.update(0,0,0); g[0]=inf; // T.prt(1,1,n+m+5);cout<<endl; for(int i=1;i<=n;i++){ int L=lower_bound(b+1,b+m+1,a[i])-b-1,R=upper_bound(b+1,b+m+1,a[i])-b-1; int l=lower_bound(b+1,b+m+1,a[i-1])-b-1,r=upper_bound(b+1,b+m+1,a[i-1])-b-1; g[i]=T.query(0,L); T.update1(L+1,R); T.add(); T.update(l+1,m,g[i-1]+1); T.update2(L+1,R); if(a[i]>=a[i-1])g[i]=min(g[i],g[i-1]); } int ans=min(g[n],T.query(1,m)); printf("%lld",ans>=inf?-1ll:ans); } signed main(){ // freopen("1.in","r",stdin);freopen("1.out","w",stdout); slv(); // cerr<<(clock()*1.0)/CLOCKS_PER_SEC<<"s"<<endl; return 0; }