#include <bits/stdc++.h>
using namespace std;
const int maxint = -1u >> 1;
const int maxn = 300000 + 10;
struct node {
  int v, cnt1, cnt2;
  node() {}
  node(int _v, int _cnt1, int _cnt2) : v(_v), cnt1(_cnt1), cnt2(_cnt2) {}
};
int n, a[maxn], p[maxn];
node c[maxn * 5];
int tag[maxn * 5];
void build(int n, int l, int r) {
  c[n] = node(1, r - l + 1, 0);
  tag[n] = 0;
  if (l == r) {
    return;
  }
  int mid = (l + r) / 2;
  build(n * 2, l, mid);
  build(n * 2 + 1, mid + 1, r);
}
inline void norm(int n, int l, int r) {
  if (tag[n]) {
    c[n * 2].v += tag[n];
    tag[n * 2] += tag[n];
    c[n * 2 + 1].v += tag[n];
    tag[n * 2 + 1] += tag[n];
    tag[n] = 0;
  }
}
inline node merge(node x1, node x2) {
  if (x2.v < x1.v) swap(x1, x2);
  if (x1.v == x2.v) {
    x1.cnt1 += x2.cnt1;
    x1.cnt2 += x2.cnt2;
  } else if (x1.v + 1 == x2.v) {
    x1.cnt2 += x2.cnt1;
  }
  return x1;
}
void update(int n, int l, int r, int ll, int rr, int delta) {
  if (r < ll || rr < l) return;
  if (ll <= l && r <= rr) {
    c[n].v += delta;
    tag[n] += delta;
    return;
  }
  norm(n, l, r);
  int mid = (l + r) / 2;
  update(n * 2, l, mid, ll, rr, delta);
  update(n * 2 + 1, mid + 1, r, ll, rr, delta);
  c[n] = merge(c[n * 2], c[n * 2 + 1]);
}
node find(int n, int l, int r, int ll, int rr) {
  if (r < ll || rr < l) return node(maxn, 0, 0);
  if (ll <= l && r <= rr) {
    return c[n];
  }
  norm(n, l, r);
  int mid = (l + r) / 2;
  node x1 = find(n * 2, l, mid, ll, rr);
  node x2 = find(n * 2 + 1, mid + 1, r, ll, rr);
  return merge(x1, x2);
}
int main() {
  while (scanf("%d", &n) == 1) {
    for (int i = 1; i <= n; ++i) {
      scanf("%d", &a[i]);
      p[a[i]] = i;
    }
    build(1, 1, n);
    long long ans = 0;
    for (int i = n; i > 0; --i) {
      int pos = p[i];
      int x1 = n + 1, x2 = n + 1;
      if (pos > 1 && a[pos - 1] > i) x1 = a[pos - 1];
      if (pos < n && a[pos + 1] > i) x2 = a[pos + 1];
      if (x1 > x2) swap(x1, x2);
      if (x1 - i > 1) {
        update(1, 1, n, i + 1, x1 - 1, 1);
      }
      if (x2 <= n) {
        update(1, 1, n, x2, n, -1);
      }
      node res = find(1, 1, n, i, n);
      ans += res.cnt1 + res.cnt2;
    }
    printf("%I64d\n", ans - n);
  }
  return 0;
}
