#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int N = 4e5;
int num[N + 1],n;
map<int,vector<int>> mp;
struct node{
int len = 0,val = 0,sum = 0;
};
int lz[4*N + 1];
node seg[4*N + 1];
void build(int id,int l,int r) {
seg[id].len = (r - l + 1);
if(l == r) {
return;
}
int mid = (l + r)/2;
build(id*2,l,mid);
build(id*2 + 1,mid + 1,r);
}
node merge(node i1,node i2) {
node res;
res.len = i1.len + i2.len;
res.val = (i1.val + i1.sum * i2.len + i2.val);
res.sum = (i1.sum + i2.sum);
return res;
}
void add(int id,int l,int r,int x) {
lz[id] += x;
int sz = seg[id].len,asd = (sz + 1) * sz / 2;
seg[id].sum += (x * sz);
seg[id].val += (x * asd);
}
void down(int id,int l,int r) {
int t = lz[id];
if(lz[id] == 0) return;
lz[id] = 0;
int mid = (l + r)/2;
add(id*2,l,mid,t);
add(id*2 + 1,mid + 1,r,t);
}
void update(int id,int l,int r,int u,int v,int x) {
if(v < l || u > r) return;
if(u <= l && v >= r) {
add(id,l,r,x);
return;
}
down(id,l,r);
int mid = (l + r)/2;
update(id*2,l,mid,u,v,x);
update(id*2 + 1,mid + 1,r,u,v,x);
seg[id] = merge(seg[id*2],seg[id*2 + 1]);
}
node query(int id,int l,int r,int u,int v) {
if(v < l || u > r) return {0,0,0};
if(u <= l && v >= r) {
// cout<<l<<" "<<r<<endl;
// cout<<seg[id].len<<" "<<seg[id].val<<" "<<seg[id].sum<<endl;
return seg[id];
}
down(id,l,r);
int mid = (l + r)/2;
return merge(query(id*2,l,mid,u,v),query(id*2 + 1,mid + 1,r,u,v));
}
struct change{
int l,r,x;
};
vector<change> thay;
inline void upd(int l,int r,int x) {
thay.push_back({l,r,-x});
update(1,0,2*n,l,r,x);
}
int res = 0;
inline void cal(vector<int> st) {
int lst = 0;
upd(n - (st[0] - 1),n,1);
for(int i = 0;i < st.size();i++) {
int nxt;
lst++;
if(i < st.size() - 1) {
nxt = st[i + 1] - 1;
} else {
nxt = n;
}
node tmp = query(1,0,2*n,2*lst + n - nxt - 1,2*lst + n - st[i] - 1);
res += tmp.val;
tmp = query(1,0,2*n,0,2*lst + n - nxt - 2);
res += tmp.sum * (nxt - st[i] + 1);
upd(n - nxt + 2*lst,n - st[i] + 2*lst,1);
}
for(auto u : thay) {
update(1,0,2*n,u.l,u.r,u.x);
}
thay.clear();
}
signed main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
cin>>n;
for(int i = 1;i <= n;i++) {
cin>>num[i];
mp[num[i]].push_back(i);
}
build(1,0,2*n);
for(auto u : mp) {
cal(u.second);
}
cout<<res<<endl;
}
