#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
#define fi first
#define se second
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=1e6+5;
int n,V,a[N],cnt[N],tot,rt[N],ans;
vector<int>g[N],ad[N];vector<P>h[N];
namespace MEX
{
	struct node{int ls,rs,x;}b[N*22];
	void build(int l,int r,int &wz)
	{
		b[wz=++tot]={0,0,0};if(l==r) return;
		int mid=(l+r)>>1;build(l,mid,b[wz].ls);build(mid+1,r,b[wz].rs);
	}
	void updata(int l,int r,int &wz,int wz1,int x,int y)
	{
		b[wz=++tot]=b[wz1];if(l==r) return b[wz].x=y,void();
		int mid=(l+r)>>1;
		if(x<=mid) updata(l,mid,b[wz].ls,b[wz1].ls,x,y);
		else updata(mid+1,r,b[wz].rs,b[wz1].rs,x,y);
		b[wz].x=min(b[b[wz].ls].x,b[b[wz].rs].x);
	}
	int query(int l,int r,int wz,int x)
	{
		if(l==r) return l;int mid=(l+r)>>1;
		if(b[b[wz].ls].x<x) return query(l,mid,b[wz].ls,x);
		return query(mid+1,r,b[wz].rs,x);
	}
	inline int que(int l,int r){return query(0,V,rt[r],l);}
}using MEX::que;
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;
	V=n+3;for(int i=0;i<=V;i++) g[i].push_back(0);
	for(int i=1;i<=n;i++) cin>>a[i],a[i]--,g[a[i]].push_back(i);
	MEX::build(1,V,rt[0]);for(int i=1;i<=n;i++) MEX::updata(0,V,rt[i],rt[i-1],a[i],i);
	for(int i=0;i<=V;i++) g[i].push_back(n+1);
	for(int i=1;i<=n;i++) a[i]?h[0].push_back({i,i}):h[1].push_back({i,i});
	for(int i=1;i<=V;i++)
	{
		for(auto [l,r]:h[i-1])
		{
			#define all g[i-1].begin(),g[i-1].end()
			int L=*(--lower_bound(all,l)),R=*upper_bound(all,r);
			if(L) h[que(L,r)].push_back({L,r});
			if(R<=n) h[que(l,R)].push_back({l,R});
		}sort(h[i].begin(),h[i].end(),[](P x,P y){return x.fi==y.fi?x.se<y.se:x.fi>y.fi;});
		vector<P>G;int las=2e9;
		for(auto [l,r]:h[i]) if(las>r) G.push_back({l,r}),las=r;swap(G,h[i]);
	}
	for(int i=1;i<=V;i++)
		for(auto [l,r]:h[i])
		{
			#define all g[i].begin(),g[i].end()
			int L=*(--lower_bound(all,l))+1,R=*upper_bound(all,r)-1;
			ans+=(r-l+1==i);
		}
	return cout<<ans,0;
}