#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <set>
#include <map>
#include <complex>
#include <iostream>
#include <time.h>
#include <math.h>
#include <stack>
#include <stdlib.h>
#include <memory.h>
#include <bitset>
#include <math.h>
#include <string>
#include <string.h>
#include <queue>
#include <vector>

using namespace std;

const int MaxN = 5e5 + 10;
const int SHIFT = 5e5 + 10;
const int INF = 1e9;
const int MOD = 1e9 + 7;

struct Node {
  int sum, add;
} t[8 * SHIFT];

int n, a[MaxN];
vector < int > c[MaxN];

void compress(int a[], int n) {
  vector < int > b;
  for (int i = 1; i <= n; ++i) {
    b.push_back(a[i]);
  }
  sort(b.begin(), b.end());
  b.resize(unique(b.begin(), b.end()) - b.begin());
  for (int i = 1; i <= n; ++i) {
    a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
  }
}

void push(int v, int l, int r) {
  if (t[v].add != 0) {
    t[v].sum += (r - l + 1) * t[v].add;
    if (l != r) {
      t[v + v].add += t[v].add;
      t[v + v + 1].add += t[v].add;
    }
    t[v].add = 0;
  }
}

void upd(int v, int L, int R, int l, int r, int val) {
  push(v, L, R);
  if (l > R || r < L) {
    return;
  }
  if (l <= L && R <= r) {
    t[v].add += val;
    push(v, L, R);
    return;
  }
  int M = (L + R) / 2;
  upd(v + v, L, M, l, r, val);
  upd(v + v + 1, M + 1, R, l, r, val);
  t[v].sum = t[v + v].sum + t[v + v + 1].sum;
}

int get(int v, int L, int R, int l, int r) {
  push(v, L, R);
  if (L == l && r == R) {
    return t[v].sum;
  }
  int M = (L + R) / 2, res = 0;
  push(v + v, L, M);
  push(v + v + 1, M + 1, R);
  if (r <= M) {
    res += get(v + v, L, M, l, r);
  } else if (l > M) {
    res += get(v + v + 1, M + 1, R, l, r);
  } else {
    res += get(v + v, L, M, l, M) +
      get(v + v + 1, M + 1, R, M + 1, r);
  }
  t[v].sum = t[v + v].sum + t[v + v + 1].sum;
  return res;
}

long long solve(vector < int > &occur) {
  occur.push_back(n + 1);
  vector < pair < int, int > > changes;
  int r = SHIFT - 0, l = SHIFT - (occur[0] - 1);
  changes.push_back(make_pair(l, r));
//  cout << l - SHIFT << ' ' << r - SHIFT << endl;
  upd(1, 1, 2 * SHIFT, l, r, +1);
  long long ans = 0LL;
  for (int i = 0; i + 1 < (int)occur.size(); ++i) {
    int l = 2 * (i + 1) - (occur[i + 1] - 1) + SHIFT;
    int r = 2 * (i + 1) - occur[i] + SHIFT;
    for (int j = r - 1, add = 1; j >= l - 1 && add != 0; --j) {
      add = get(1, 1, 2 * SHIFT, 1, j);
      ans += add;
    }
    changes.push_back(make_pair(l, r));
    upd(1, 1, 2 * SHIFT, l, r, +1);
  }
  for (int i = 0; i < (int)changes.size(); ++i) {
    int l = changes[i].first, r = changes[i].second;
    upd(1, 1, 2 * SHIFT, l, r, -1);
  }
  return ans;
}

int main() {
//  freopen("input.txt", "r", stdin);
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  compress(a, n);
  for (int i = 1; i <= n; ++i) {
    c[a[i]].push_back(i);
  }
  long long ans = 0LL;
  for (int i = 0; i < n; ++i) {
    if (!c[i].empty()) {
      ans += solve(c[i]);
    }
  }
  cout << ans << '\n';
  return 0;
}