#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;
}