#include<bits/stdc++.h> #define int long long #define f first #define s second #define mp(x,y) make_pair(x,y) using namespace std; inline int read(){ int x=0,f=0;char c=getchar(); while(c<48||c>57)f|=(!(c^'-')),c=getchar(); while(c>=48&&c<=57)x=(x<<1)+(x<<3)+(c^48),c=getchar(); return f?-x:x; } deque<pair<int,int> >q,qq; int n,ans,a[10005]; signed main(){ n=read(); if(n<=1000){ for(int i=1;i<=n;i++){a[i]=read();for(int j=1;j<i;j++)if(a[i]<a[j]){ans+=i-j;break;}} cout<<ans<<endl; return 0; } for(int i=1,x;i<=n;i++){ x=read(); while(!q.empty()&&q.front().f<=x)qq.push_back(q.front()),q.pop_front(); q.push_back(mp(x,i)),ans+=i-q.front().s; while(!qq.empty())q.push_front(qq.back()),qq.pop_back(); } cout<<ans<<endl; return 0; }