#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 12;
const int inf = 0x3f3f3f3f;
int n, pos[N], Time[N], cnt[N];
long long ans;
int Tmin1[N], Smin1[N];
int Tmin2[N], Smin2[N];
int add[N];
void pushup(int now) {
  if (Tmin1[now << 1] <= Tmin1[now << 1 | 1]) {
    Tmin1[now] = Tmin1[now << 1];
    Smin1[now] = Smin1[now << 1];
    if (Tmin1[now << 1] == Tmin1[now << 1 | 1]) {
      Smin1[now] += Smin1[now << 1 | 1];
      if (Tmin2[now << 1] <= Tmin2[now << 1 | 1]) {
        Tmin2[now] = Tmin2[now << 1];
        Smin2[now] = Smin2[now << 1];
        if (Tmin2[now << 1] == Tmin2[now << 1 | 1])
          Smin2[now] += Smin2[now << 1 | 1];
      } else {
        Tmin2[now] = Tmin2[now << 1 | 1];
        Smin2[now] = Smin2[now << 1 | 1];
      }
    } else {
      if (Tmin2[now << 1] <= Tmin1[now << 1 | 1]) {
        Tmin2[now] = Tmin2[now << 1];
        Smin2[now] = Smin2[now << 1];
        if (Tmin2[now << 1] == Tmin1[now << 1 | 1])
          Smin2[now] += Smin1[now << 1 | 1];
      } else {
        Tmin2[now] = Tmin1[now << 1 | 1];
        Smin2[now] = Smin1[now << 1 | 1];
      }
    }
  } else {
    Tmin1[now] = Tmin1[now << 1 | 1];
    Smin1[now] = Smin1[now << 1 | 1];
    if (Tmin1[now << 1] <= Tmin2[now << 1 | 1]) {
      Tmin2[now] = Tmin1[now << 1];
      Smin2[now] = Smin1[now << 1];
      if (Tmin1[now << 1] == Tmin2[now << 1 | 1])
        Smin2[now] += Smin2[now << 1 | 1];
    } else {
      Tmin2[now] = Tmin2[now << 1 | 1];
      Smin2[now] = Smin2[now << 1 | 1];
    }
  }
}
void pushdown(int now) {
  Tmin1[now << 1] += add[now];
  Tmin1[now << 1 | 1] += add[now];
  Tmin2[now << 1] += add[now];
  Tmin2[now << 1 | 1] += add[now];
  add[now << 1] += add[now];
  add[now << 1 | 1] += add[now];
  add[now] = 0;
}
void modify(int now, int l, int r, int x, int y, int z) {
  if (x <= l && r <= y) {
    Tmin1[now] += z;
    Tmin2[now] += z;
    add[now] += z;
    return;
  }
  if (add[now]) pushdown(now);
  int mid = (l + r) >> 1;
  if (x <= mid) modify(now << 1, l, mid, x, y, z);
  if (y > mid) modify(now << 1 | 1, mid + 1, r, x, y, z);
  pushup(now);
}
int query(int now, int l, int r, int x, int y) {
  if (l > y || r < x) return 0;
  if (x <= l && r <= y) {
    int res = 0;
    if (Tmin1[now] <= 2) res += Smin1[now];
    if (Tmin2[now] <= 2) res += Smin2[now];
    return res;
  }
  if (add[now]) pushdown(now);
  int mid = (l + r) >> 1;
  return query(now << 1, l, mid, x, y) + query(now << 1 | 1, mid + 1, r, x, y);
}
void build(int now, int l, int r) {
  Smin1[now] = 1;
  Tmin2[now] = inf;
  if (l == r) return;
  int mid = (l + r) >> 1;
  build(now << 1, l, mid);
  build(now << 1 | 1, mid + 1, r);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    int p;
    scanf("%d", &p);
    pos[p] = i;
  }
  build(1, 1, n);
  for (int i = 1; i <= n; i++) {
    Time[pos[i]] = i;
    if (cnt[pos[i] - 1] && cnt[pos[i] + 1]) {
      int l = max(Time[pos[i] - 1], Time[pos[i] + 1]);
      int r = min(Time[pos[i] - 1], Time[pos[i] + 1]);
      modify(1, 1, n, l + 1, i, 1);
      modify(1, 1, n, 1, r, -1);
    } else if (cnt[pos[i] - 1])
      modify(1, 1, n, Time[pos[i] - 1] + 1, i, 1);
    else if (cnt[pos[i] + 1])
      modify(1, 1, n, Time[pos[i] + 1] + 1, i, 1);
    else
      modify(1, 1, n, 1, i, 1);
    if (i > 1) ans += query(1, 1, n, 1, i - 1);
    cnt[pos[i]]++;
  }
  printf("%lld", ans);
  return 0;
}
