#include<bits/stdc++.h>
using namespace std;
int n,m,a[100010],v[100010],V[100010],sum,V2[100010],ans;

bool check(int x){
    int i;
    for(i=x-n+1;i>=1;i-=n){
    	if(!V2[i]) return false;
	} 
    i+=n;
    if(i-1>0&&!V[i-1]) return false;
    return true;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) scanf("%d",&a[i]);
    for(int i=1;i<=min(n,m);i++){
        v[a[i]]++;
        if(v[a[i]]==2) sum++;
        if(!sum) V[i]=1;
    }
    if(!sum) V2[1]=1;
    for (int i=n+1;i<=m;i++){
        v[a[i]]++;
        if(v[a[i]]==2) sum++;
        v[a[i-n]]--;
        if(v[a[i-n]]==1) sum--;
        if(!sum) V2[i-n+1]=1;
    }
    memset(v,0,sizeof(v));
    sum=0;
    int i=0;
    for(i=m;i>=1;i--){
        v[a[i]]++;
        if(v[a[i]]>=2) break;
    }
    for(int j=m;j>max(0,m-n);j--){
    	if (i<=j && check(j)) ans++;
	}
    if(ans) printf("%d\n",(n>=m&&ans==m?n:ans));
    else printf("0\n");
    return 0;
}