#include <bits/stdc++.h>

#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) int((a).size())

using ll = long long;
using ull = unsigned long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

template<class T> void chkmx(T &x, T y) { if (y > x) x = y; }
template<class T> void chkmn(T &x, T y) { if (y < x) x = y; }

using namespace std;

const int maxn = 2000010;
const int base = 2000000;
mt19937 rnd(114514);

int n, a[maxn], cntl[maxn << 1], cntr[maxn << 1];

int main() {
  // freopen("median.in", "r", stdin);
  // freopen("median.out", "w", stdout);
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  cin >> n;
  rep (i, 1, n) cin >> a[i];
  // rep (i, 1, n) a[i] = i;
  // shuffle(a + 1, a + n + 1, rnd);
  ll ans = 0;
  rep (i, 1, n) {
    int lim = 2e5 / pow(max(1, abs(a[i] - n / 2)), .75);
    int s0 = 0, s1 = 0, mxf = 0, mxg = 0, mnf = 0, mng = 0, l = i, r = i;
    ll s = 1;
    cntl[base]++, cntr[base]++;
    while (true) {
      if (abs(s0 + s1) > lim || (l == 1 && r == n)) break;
      if (l > 1) {
        --l, s0 += (a[l] < a[i] ? -1 : 1);
        s += cntr[base - s0] + cntr[base - s0 + 1];
        cntl[s0 + base]++;
        chkmn(mnf, s0), chkmx(mxf, s0);
      }
      if (r < n) {
        ++r, s1 += (a[r] < a[i] ? -1 : 1);
        s += cntl[base - s1] + cntl[base - s1 + 1];
        cntr[s1 + base]++;
        chkmn(mng, s1), chkmx(mxg, s1);
      }
    }
    rep (i, mnf, mxf) cntl[i + base] = 0;
    rep (i, mng, mxg) cntr[i + base] = 0;
    ans += s * a[i];
  }
  cout << ans << '\n';
}