#include <iostream>
#include <vector>

struct S {
  int min, max;
  S(int in = +0x3b9aca00, int ax = -0x3b9aca00) { min = in, max = ax; }
};
using F = int;
S e() { return S(); }
S op(S lhs, S rhs) { return S(std::min(lhs.min, rhs.min), std::max(lhs.max, rhs.max)); }
S mapping(F f, S x) { return S(x.min + f, x.max + f); }
F composition(F lhs, F rhs) { return lhs + rhs; }
F id() { return 0; }

S t[8000007];
F lazy[8000007];
void set(int p, F f) {
  t[p] = mapping(f, t[p]);
  lazy[p] = composition(lazy[p], f);
}
void pushdown(int p) {
  set(p << 1, lazy[p]), set(p << 1 | 1, lazy[p]);
  lazy[p] = id();
}
void pushup(int p) { t[p] = op(t[p << 1], t[p << 1 | 1]); }
void build(int p, int l, int r) {
  int mid = (l + r) >> 1;
  if (l == r) {
    t[p] = S(mid, mid);
    return;
  }
  build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
  pushup(p);
}
void modify(int p, int l, int r, int ql, int qr, F f) {
  if (ql <= l && r <= qr) {
    set(p, f);
    return;
  }
  pushdown(p);
  int mid = (l + r) >> 1;
  if (ql <= mid) {
    modify(p << 1, l, mid, ql, qr, f);
  }
  if (qr > mid) {
    modify(p << 1 | 1, mid + 1, r, ql, qr, f);
  }
  pushup(p);
}
S query(int p, int l, int r, int ql, int qr) {
  if (ql <= l && r <= qr) {
    return t[p];
  }
  pushdown(p);
  S ans = e();
  int mid = (l + r) >> 1;
  if (ql <= mid) {
    ans = op(query(p << 1, l, mid, ql, qr), ans);
  }
  if (qr > mid) {
    ans = op(ans, query(p << 1 | 1, mid + 1, r, ql, qr));
  }
  return ans;
}
void dfs(int p, int l, int r, int ql, int qr, std::vector<int>& c, S f) {
  int mid = (l + r) >> 1;
  if (ql <= l && r <= qr) {
    if (t[p].max < f.min || t[p].min > f.max) {
      return;
    }
    if (l == r) {
      ++c[t[p].min - f.min];
      return;
    }
    pushdown(p);
    dfs(p << 1, l, mid, ql, qr, c, f);
    dfs(p << 1 | 1, mid + 1, r, ql, qr, c, f);
    return;
  }
  pushdown(p);
  if (ql <= mid) {
    dfs(p << 1, l, mid, ql, qr, c, f);
  }
  if (qr > mid) {
    dfs(p << 1 | 1, mid + 1, r, ql, qr, c, f);
  }
}


int n, p[2000007], q[2000007];

int main() {
  std::cin.tie(nullptr)->sync_with_stdio(false);
  std::cin >> n;
  for (int i = 1; i <= n; ++i) {
    std::cin >> p[i];
    q[p[i]] = i;
  }
  build(1, 0, n);
  long long ans = 0;
  for (int i = 1; i <= n; ++i) {
    if (i != 1) {
      modify(1, 0, n, q[i - 1], n, -1);
    }
    modify(1, 0, n, q[i], n, -1);
    auto L = query(1, 0, n, 0, q[i] - 1);
    auto R = query(1, 0, n, q[i], n);
    S And(std::max(L.min, R.min), std::min(L.max, R.max));
    if (And.min <= And.max) {
      std::vector<int> cl(And.max - And.min + 1), cr(And.max - And.min + 1);
      dfs(1, 0, n, 0, q[i] - 1, cl, And);
      dfs(1, 0, n, q[i], n, cr, And);
      for (int j = 0; j <= And.max - And.min; ++j) {
        ans += 1LL * cl[j] * cr[j] * i;
      }
    }
    And = S(std::max(L.min, R.min - 1), std::min(L.max, R.max - 1));
    if (And.min <= And.max) {
      std::vector<int> cl(And.max - And.min + 1), cr(And.max - And.min + 1);
      dfs(1, 0, n, 0, q[i] - 1, cl, And);
      dfs(1, 0, n, q[i], n, cr, S(And.min + 1, And.max + 1));
      for (int j = 0; j <= And.max - And.min; ++j) {
        ans += 1LL * cl[j] * cr[j] * i;
      }
    }
  }
  std::cout << ans << '\n';
  return 0;
}