#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; const int maxn=1e6+10,inf=1e9; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,m,a[maxn],b[maxn],arr[maxn],brr[maxn]; struct SegTree { struct nd { int mx,lz; nd(){lz=1e9;} void push(int x){mx=min(mx,x),lz=min(lz,x);} }d[maxn<<2]; #define ls(p) (p<<1) #define rs(p) (p<<1|1) void pu(int p){d[p].mx=min(d[ls(p)].mx,d[rs(p)].mx);} void pd(int p){d[ls(p)].push(d[p].lz),d[rs(p)].push(d[p].lz),d[p].lz=1e9;} void modify(int l,int r,int s,int t,int p,int x){ if(l<=s&&t<=r)return d[p].push(x),void();pd(p); int mid=s+t>>1; if(l<=mid)modify(l,r,s,mid,ls(p),x);if(r>mid)modify(l,r,mid+1,t,rs(p),x);pu(p); } int ask(int l,int r,int s,int t,int p){ if(l>r)return 1e9; if(l<=s&&t<=r)return d[p].mx;pd(p); int mid=s+t>>1,res=1e9; if(l<=mid)res=min(res,ask(l,r,s,mid,ls(p)));if(r>mid)res=min(res,ask(l,r,mid+1,t,rs(p))); return res; } void print(int l,int r,int s,int t,int p){ if(s==t)return arr[s+m]=d[p].mx,void();pd(p); int mid=s+t>>1; if(l<=mid)print(l,r,s,mid,ls(p));if(r>mid)print(l,r,mid+1,t,rs(p)); } void rebuild(int l,int r,int s,int t,int p){ if(s==t)return d[p].mx=arr[s+m],void();pd(p); int mid=s+t>>1; if(l<=mid)rebuild(l,r,s,mid,ls(p));if(r>mid)rebuild(l,r,mid+1,t,rs(p));pu(p); } }T; int f[maxn]; void slv(){ n=read(),m=read();up(i,1,n)a[i]=read();up(i,1,m)b[i]=read(); sort(b+1,b+m+1); memset(arr,0x3f,sizeof(arr)); arr[m]=0;T.rebuild(-m,m,-m,m,1); up(i,1,n){ f[i]=(a[i-1]<=a[i])?f[i-1]:inf; int loc=lower_bound(b+1,b+m+1,a[i])-b-1; f[i]=min(f[i],T.ask(-m,loc-(i-1),-m,m,1)+i-1); loc=lower_bound(b+1,b+m+1,a[i])-b; if(b[loc]==a[i]){ int l=loc,r=loc; while(r<=m&&b[r+1]==b[loc])r++; T.print(l-(i-1),r-(i-1),-m,m,1); up(p,l-(i-1)-1,r-(i-1)-1)brr[p+m]=arr[p+m+1]; up(p,l-(i-1)-1,r-(i-1)-1)arr[p+m]=brr[p+m]-1; T.rebuild(l-(i-1)-1,r-(i-1)-1,-m,m,1); } loc=lower_bound(b+1,b+m+1,a[i-1])-b; T.modify(loc-i,m,-m,m,1,f[i-1]+1-i); } int res=min(f[n],T.ask(-m,m-n,-m,m,1)+n); cout<<((res<=m)?res:-1); } int main(){ //freopen("sort.in","r",stdin),freopen("sort.out","w",stdout); slv(); return 0; }