#include <bits/stdc++.h>
using namespace std;
const int maxn = 310000;
int n, A[maxn], B[maxn];
struct Tseg {
  int x, y;
  Tseg *l, *r;
  int M, P, Q, B;
  inline void spread() {
    if (!B) return;
    l->M += B, l->B += B;
    r->M += B, r->B += B;
    B = 0;
  }
  inline void update() {
    M = min(l->M, r->M);
    P = (M == l->M ? l->P : 0) + (M == r->M ? r->P : 0);
    Q = (M == l->M       ? l->Q
         : M + 1 == l->M ? l->P
                         : 0) +
        (M == r->M       ? r->Q
         : M + 1 == r->M ? r->P
                         : 0);
  }
  void add(int a, int b, int v) {
    if (x == a && y == b) return M += v, B += v, void();
    int mid = x + y >> 1;
    spread();
    b <= mid  ? l->add(a, b, v)
    : a > mid ? r->add(a, b, v)
              : (l->add(a, mid, v), r->add(mid + 1, b, v));
    update();
  }
} * St;
struct Tmemory {
  int n;
  Tseg buf[maxn * 3];
  inline Tseg *operator()() { return buf + n++; }
} newS;
namespace Ninit {
Tseg *build(int x, int y) {
  Tseg *p = newS();
  p->x = x, p->y = y;
  if (x == y) return p->M = 1, p->P = 1, p;
  int mid = x + y >> 1;
  p->l = build(x, mid), p->r = build(mid + 1, y);
  p->update();
  return p;
}
void init() {
  int i;
  scanf("%d", &n);
  for (i = 1; i <= n; ++i) scanf("%d", B + i), A[B[i]] = i;
  St = build(1, n);
}
}  // namespace Ninit
namespace Nsolve {
long long ans;
void solve() {
  int i, a, b;
  for (i = 1; i <= n; ++i) {
    a = (B[A[i] - 1] < i ? B[A[i] - 1] : 0),
    b = (B[A[i] + 1] < i ? B[A[i] + 1] : 0);
    if (a > b) swap(a, b);
    if (b + 1 <= i - 1) St->add(b + 1, i - 1, 1);
    if (a >= 1) St->add(1, a, -1);
    ans += St->P + St->Q - n + i - 1;
  }
  cout << ans << endl;
}
}  // namespace Nsolve
int main() {
  Ninit::init();
  Nsolve::solve();
  return 0;
}
