#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
typedef long long int lld;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
bool in[2000000];
int arr[2000000];
const int MAX=1e6;
vector<pair<int,int> >Q;
class ST{
	pair<lld,int> M[4*MAX];
	public:
	void build(int a, int b, int node){
		if(a==b){
			M[node]={arr[a],a};
			return;
		}
		int mid=(a+b)/2;
		build(a,mid,2*node);
		build(mid+1,b,2*node+1);
		M[node]=max(M[2*node],M[2*node+1]);
	}
	pair<lld,int> query(int a, int b, int node, int l, int r){
		if(r<a || b<l)return {-1,-1};
		if(l<=a && b<=r)return M[node];
		int mid=(a+b)/2;
		return max(query(a,mid,2*node,l,r),query(mid+1,b,2*node+1,l,r));
	}
};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using ui64 = unsigned long long;
ui64 gerar(ui64 lo, ui64 hi) { return uniform_int_distribution<ui64>(lo,hi)(rng); }
using namespace chrono;

ST S;
int n;
void process(int a, int b){
	if(a>b)return;
	pair<lld,int> p=S.query(0,n-1,1,a,b);
	int pos=p.second;
	int val=p.first;
	rep(i,max(a,pos+1-val),min(b,pos)+1){
		if(i+val-1>b)break;
		Q.push_back({i,i+val-1});
	}
	process(a,pos-1);
	process(pos+1,b);
}

vector<bool> W;
lld hsh[1000000];
lld pref[1000000];
lld tar[1000000];
void Tr(){
	rep(i,0,n){
		hsh[i]=gerar(0,1e9);
	}
	pref[0]=0;
	rep(i,0,n){
		pref[i+1]=pref[i]+hsh[arr[i]-1];
	}
	tar[0]=0;
	rep(i,0,n){
		tar[i+1]=tar[i]+hsh[i];
	}
	rep(i,0,(int)Q.size()){
		int l=Q[i].first;
		int r=Q[i].second;
		if(tar[r-l+1]!=pref[r+1]-pref[l]){
			W[i]=false;
		}
	}
}
void solve(){
	cin>>n;
	
	rep(i,0,n){
		cin>>arr[i];
	}
	S.build(0,n-1,1);
	process(0,n-1);
	W.resize(Q.size(),true);
	rep(t,0,4){
		Tr();
	}
	lld ans=0;
	trav(a,W)ans+=a;
	cout<<ans<<"\n";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt=1;
	//cin>>tt;
	while(tt--){
		solve();
	}
}