#include <bits/stdc++.h>

#define ll long long
#define fi first
#define se second

using namespace std;

const int maxn = 1e6 + 10, B = 31337, mod = 998244353;

int n;
ll ans = 0;
int arr[maxn];
int maks[maxn];
int h[maxn];
unordered_map <int, int> l;
unordered_map <int, int> r;
int pref[maxn];
int pot[maxn];

int add(int a, int b){
	return (a + b) % mod;
}

int mul(int a, int b){
	return ((ll)a * b) % mod;
}

int sub(int a, int b){
	return (a - b + mod) % mod;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	pot[0] = 1;
	for(int i = 1; i < maxn; i++){
		pot[i] = mul(pot[i - 1], B);
	}
	
	for(int i = 2; i < maxn; i++){
		pref[i] = add(pref[i - 1], pot[i]);
	}
	
	cin >> n;
	
	for(int i = 1; i <= n; i++){
		cin >> arr[i];
	}
	
	for(int i = 1; i <= n; i++){
		if(arr[i] != 1) continue;
		
//		cout << i << endl;
		
		ans++;
		maks[i] = 1;
		h[i] = 0;
		l.clear();
		r.clear();
		l[0] = 1;
		r[0] = 1;
		
		for(int j = i - 1; j >= 1; j--){
			if(arr[j] == 1) break;
			
			maks[j] = max(maks[j + 1], arr[j]);
			h[j] = add(h[j + 1], pot[arr[j]]);
			l[h[j]]++;
		}
		
		for(int j = i + 1; j <= n; j++){
			if(arr[j] == 1) break;
			
			maks[j] = max(maks[j - 1], arr[j]);
			h[j] = add(h[j - 1], pot[arr[j]]);
			r[h[j]]++;
			
			ans += l[sub(pref[maks[j]], h[j])];
//			cout << "r: " << j << "  +" << l[sub(pref[maks[j]], h[j])] << ' ' << sub(pref[maks[j]], h[j]) << endl;
		}
		
		for(int j = i - 1; j >= 1; j--){
			if(arr[j] == 1) break;
			
			ans += r[sub(pref[maks[j]], h[j])];
			
//			cout << "l: " << j << "  +" << r[sub(pref[maks[j]], h[j])] << endl;
		}
	}
	
	cout << ans;
	
	return 0;
}