#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[1000005],m;
deque<int>q;
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++)
	{
		while(!q.empty()&&q.front()+m<=i)
			q.pop_front();
		while(!q.empty()&&a[q.back()]<=a[i])
			q.pop_back();
		q.push_back(i);
		if(i>=m)
			cout<<q.size()<<'\n';
	}
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[1000005],m;
deque<int>q;
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++)
	{
		while(!q.empty()&&q.front()+m<=i)
			q.pop_front();
		while(!q.empty()&&a[q.back()]<a[i])
			q.pop_back();
		q.push_back(i);
		if(i>=m)
			cout<<q.size()<<'\n';
	}
	return 0;
}

  #include<bits/stdc++.h>
#define int long long
using namespace std;
struct N
{
	int id,wz;
}a[1000005];
int n,k,ans;
map<int,int>mp;
bool cmp(N x,N y)
{
	return x.wz<y.wz;
}
bool check(int x)
{
	mp.clear();
	int sum=0;
	for(int i=1;i<x;i++)
	{
		mp[a[i].wz]++;
		if(mp[a[i].wz]==1)
			sum++;
	}
	for(int i=x;i<=n;i++)
	{
		mp[a[i].wz]++;
		if(mp[a[i].wz]==1)
			sum++;
		if(i!=x)
		{
			mp[a[i-x].wz]--;
			if(mp[a[i-x].wz]==0)
				sum--;
		}
		if(sum==k)
		{
			ans=min(ans,x);
			return 1;
		}
	}
	return 0;
}
deque<int>q;
signed main()
{
	cin>>n>>k;
	for(int i=1;i<=k;i++)
	{
		int x;
		cin>>x;
		for(int j=1;j<=x;j++)
		{
			int z;
			cin>>z;
			a[++ans].id=x;
			a[ans].wz=z;
		}
	}
	sort(a+1,a+n+1,cmp);
	ans=1e9;
	int l=1-1,r=n+1;
	while(l+1<r)
	{
		int mid=(l+r)/2;
		if(check(mid)==1)
			r=mid;
		else
			l=mid;
	}
	cout<<ans;
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct N
{
	int id,wz;
}a[1000005];
bool cmp(N x,N y)
{
	return x.wz<y.wz;
}
map<int,int>mp;
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,k,l=1,mn=INT_MAX,cnt=0,sum=0;
	cin>>n>>k;
	for(int i=1;i<=k;i++)
    {
		int x;
		cin>>x;
		for(int j=1;j<=x;j++)
        {
			int y;
			cin>>y;
			a[++cnt]={i,y};
		}
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)
    {
		mp[a[i].id]++;
		if(mp[a[i].id]==1)
			sum++;
		while(i!=l&&mp[a[l].id]>1)
        {
			mp[a[l].id]--;
			l++;
		}
		if(sum==k)
			mn=min(a[i].wz-a[l].wz,mn);
	}
	cout<<mn<<'\n';
	return 0;
}