#include <cstdio>
#include <algorithm>
using namespace std;
#define maxn 100000
int n,a[maxn];
int hely(int v){// (növő sorrendben) rendezett "a" tömbben megkeresi v (egyik) pozicióját O(log(n)) időben, bináris keresés
int p2=1,pos=0,pos2;
while(p2<n)p2<<=1;
for(;p2;p2>>=1){
pos2=pos+p2;
if(pos2<n&&a[pos2]<=v)pos=pos2;
}
return pos;
}
int main(void){
int i,index,K,kulonbozo,t,b[maxn],tipus[maxn],szin[maxn],szam[maxn];
long long int ans;// az eredmény >2^32 is lehet!
scanf("%d",&n);
for(i=0;i<n;i++){scanf("%d",&a[i]);b[i]=a[i];}
sort(a,a+n);// állatok rendezése
K=0;
for(i=0;i<n;i++){
if(i==0||a[i]>a[i-1])K++;// új állatfaj
szin[i]=K-1;// a rendezett sorban ez a (K-1)-dik állatfaj
}
for(i=0;i<n;i++)tipus[i]=szin[hely(b[i])];// az eredeti sorrendben az i-edik állat a tipus[i]-edik állatfaj
for(i=0;i<K;i++)szam[i]=0;// szam[i] majd az i-edik álltfajt számlálja meg
ans=0;
index=0;
kulonbozo=0;// i-edik állatig a különböző állatfajok számát "kulonbozo" adja meg
for(i=0;i<n;i++){
t=tipus[i];
if(szam[t]==0)kulonbozo++;// az i-edik új állatfaj
szam[t]++;// a t-edik állatfajból eggyel több van
for(;kulonbozo==K;index++){// azt a legnagyobb indexet határozzuk meg, amelyre [index,i] mindegyik állatfajt tartalmazza
// nyilván nagyobb i-hez nagyobb index tartozik
// így ennek a ciklusnak az időgénye összesen O(n) az n értékre.
t=tipus[index];
if(szam[t]==1)break;// t-edik állatfajból 1 van, így őt nem dobhatjuk ki
szam[t]--;
}
if(kulonbozo==K)ans+=index+1;// ha volt mindegyik állatfaj, akkor az i-re végződő túrák közül
// [j,i] pontosan akkor lesz jó, ha j<=index, ezek száma index+1
}
printf("%lld\n",ans);
return 0;
}
I2luY2x1ZGUgPGNzdGRpbz4KI2luY2x1ZGUgPGFsZ29yaXRobT4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgbWF4biAxMDAwMDAKCmludCBuLGFbbWF4bl07CgppbnQgaGVseShpbnQgdil7Ly8gKG7DtnbFkSBzb3JyZW5kYmVuKSByZW5kZXpldHQgImEiIHTDtm1iYmVuIG1lZ2tlcmVzaSB2IChlZ3lpaykgcG96aWNpw7Nqw6F0IE8obG9nKG4pKSBpZMWRYmVuLCBiaW7DoXJpcyBrZXJlc8OpcwogICAgCiAgICBpbnQgcDI9MSxwb3M9MCxwb3MyOwogICAgCiAgICB3aGlsZShwMjxuKXAyPDw9MTsKICAgIGZvcig7cDI7cDI+Pj0xKXsKICAgICAgICBwb3MyPXBvcytwMjsKCWlmKHBvczI8biYmYVtwb3MyXTw9dilwb3M9cG9zMjsKICAgIH0KICAgIHJldHVybiBwb3M7Cn0KCgppbnQgbWFpbih2b2lkKXsKICAKICAgIGludCBpLGluZGV4LEssa3Vsb25ib3pvLHQsYlttYXhuXSx0aXB1c1ttYXhuXSxzemluW21heG5dLHN6YW1bbWF4bl07CiAgICBsb25nIGxvbmcgaW50IGFuczsvLyBheiBlcmVkbcOpbnkgPjJeMzIgaXMgbGVoZXQhCiAgICAKICAgIHNjYW5mKCIlZCIsJm4pOwogICAgZm9yKGk9MDtpPG47aSsrKXtzY2FuZigiJWQiLCZhW2ldKTtiW2ldPWFbaV07fQogICAgCiAgICBzb3J0KGEsYStuKTsvLyDDoWxsYXRvayByZW5kZXrDqXNlCiAgICBLPTA7CiAgICBmb3IoaT0wO2k8bjtpKyspewogICAgICBpZihpPT0wfHxhW2ldPmFbaS0xXSlLKys7Ly8gw7pqIMOhbGxhdGZhagogICAgICBzemluW2ldPUstMTsvLyBhIHJlbmRlemV0dCBzb3JiYW4gZXogYSAoSy0xKS1kaWsgw6FsbGF0ZmFqCiAgICB9CiAgICBmb3IoaT0wO2k8bjtpKyspdGlwdXNbaV09c3ppbltoZWx5KGJbaV0pXTsvLyBheiBlcmVkZXRpIHNvcnJlbmRiZW4gYXogaS1lZGlrIMOhbGxhdCBhIHRpcHVzW2ldLWVkaWsgw6FsbGF0ZmFqCiAgICBmb3IoaT0wO2k8SztpKyspc3phbVtpXT0wOy8vIHN6YW1baV0gbWFqZCBheiBpLWVkaWsgw6FsbHRmYWp0IHN6w6FtbMOhbGphIG1lZwogICAgCiAgICBhbnM9MDsKICAgIGluZGV4PTA7CiAgICBrdWxvbmJvem89MDsvLyBpLWVkaWsgw6FsbGF0aWcgYSBrw7xsw7ZuYsO2esWRIMOhbGxhdGZham9rIHN6w6Ftw6F0ICJrdWxvbmJvem8iIGFkamEgbWVnCiAgICBmb3IoaT0wO2k8bjtpKyspewogICAgICAgdD10aXB1c1tpXTsKICAgICAgIGlmKHN6YW1bdF09PTApa3Vsb25ib3pvKys7Ly8gYXogaS1lZGlrIMO6aiDDoWxsYXRmYWoKICAgICAgIHN6YW1bdF0rKzsvLyBhIHQtZWRpayDDoWxsYXRmYWpiw7NsIGVnZ3llbCB0w7ZiYiB2YW4KICAgICAgIAogICAgICAgZm9yKDtrdWxvbmJvem89PUs7aW5kZXgrKyl7Ly8gYXp0IGEgbGVnbmFneW9iYiBpbmRleGV0IGhhdMOhcm96enVrIG1lZywgYW1lbHlyZSBbaW5kZXgsaV0gbWluZGVneWlrIMOhbGxhdGZhanQgdGFydGFsbWF6emEKCSAgICAgICAgICAgICAgICAgICAgICAgICAgLy8gbnlpbHbDoW4gbmFneW9iYiBpLWhleiBuYWd5b2JiIGluZGV4IHRhcnRvemlrCgkgICAgICAgICAgICAgICAgICAgICAgICAgIC8vIMOtZ3kgZW5uZWsgYSBjaWtsdXNuYWsgYXogaWTFkWfDqW55ZSDDtnNzemVzZW4gTyhuKSBheiBuIMOpcnTDqWtyZS4KCSAgIHQ9dGlwdXNbaW5kZXhdOwoJICAgaWYoc3phbVt0XT09MSlicmVhazsvLyB0LWVkaWsgw6FsbGF0ZmFqYsOzbCAxIHZhbiwgw61neSDFkXQgbmVtIGRvYmhhdGp1ayBraQoJICAgc3phbVt0XS0tOwogICAgICAgfQogICAgICAgCiAgICAgICBpZihrdWxvbmJvem89PUspYW5zKz1pbmRleCsxOy8vIGhhIHZvbHQgbWluZGVneWlrIMOhbGxhdGZhaiwgYWtrb3IgYXogaS1yZSB2w6lnesWRZMWRIHTDunLDoWsga8O2esO8bAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAvLyBbaixpXSBwb250b3NhbiBha2tvciBsZXN6IGrDsywgaGEgajw9aW5kZXgsIGV6ZWsgc3rDoW1hIGluZGV4KzEKICAgIH0KICAgIHByaW50ZigiJWxsZFxuIixhbnMpOwogICAgCiAgICByZXR1cm4gMDsKfQo=