#include <bits/stdc++.h>
using namespace std;
int i, j, k, l, n, m, s, sum, A, C, R, tot, an;
const int N = 610000;
class arr {
 public:
  int v, s, s2, t;
} tre[N * 8];
int a[N], b[N];
void updata(int now) {
  arr l = tre[now * 2];
  arr r = tre[now * 2 + 1];
  arr w = tre[now];
  w.v = min(l.v, r.v);
  w.s = l.s * (l.v == w.v) + r.s * (r.v == w.v);
  w.s2 = l.s2 * (l.v == w.v) + r.s2 * (r.v == w.v);
  w.s2 += l.s * (l.v == w.v + 1) + r.s * (r.v == w.v + 1);
  tre[now] = w;
}
void D(int now, int v) {
  tre[now].v += v;
  tre[now].t += v;
}
void down(int now) {
  D(now * 2, tre[now].t);
  D(now * 2 + 1, tre[now].t);
  tre[now].t = 0;
}
void add(int now, int l, int r, int ll, int rr, int v) {
  if ((l == ll) && (r == rr)) {
    tre[now].v += v;
    tre[now].t += v;
    return;
  }
  if (tre[now].t) down(now);
  int mid = (l + r) / 2;
  if ((ll <= mid) && (rr <= mid))
    add(now * 2, l, mid, ll, rr, v);
  else if ((ll > mid) && (rr > mid))
    add(now * 2 + 1, mid + 1, r, ll, rr, v);
  else {
    add(now * 2, l, mid, ll, mid, v);
    add(now * 2 + 1, mid + 1, r, mid + 1, rr, v);
  }
  updata(now);
}
int find(int now, int l, int r, int ll, int rr) {
  if ((l == ll) && (r == rr)) {
    return tre[now].s2 * (tre[now].v <= 1) + tre[now].s * (tre[now].v <= 2);
  }
  if (tre[now].t) down(now);
  int mid = (l + r) / 2;
  if ((ll <= mid) && (rr <= mid))
    return find(now * 2, l, mid, ll, rr);
  else if ((ll > mid) && (rr > mid))
    return find(now * 2 + 1, mid + 1, r, ll, rr);
  else {
    return find(now * 2, l, mid, ll, mid) +
           find(now * 2 + 1, mid + 1, r, mid + 1, rr);
  }
}
void build(int now, int l, int r) {
  if (l == r) {
    tre[now].s = 1;
    return;
  }
  int mid = (l + r) / 2;
  build(now * 2, l, mid);
  build(now * 2 + 1, mid + 1, r);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]), b[a[i]] = i;
  build(1, 1, n);
  long long an = 0;
  for (int i = 1; i <= n; i++) {
    int l = a[b[i] - 1];
    int r = a[b[i] + 1];
    add(1, 1, n, 1, i, 1);
    if ((l) && (l < i)) add(1, 1, n, 1, l, -1);
    if ((r) && (r < i)) add(1, 1, n, 1, r, -1);
    if (i > 1) an += (long long)find(1, 1, n, 1, i - 1);
  }
  printf("%I64d\n", an);
  return 0;
}
