#include <bits/stdc++.h>
using namespace std;
int p[300011], q[300011], n, i, j, k, tot, f[300011];
int Left[600011], Right[600011], stop[600011], min1[600011], min2[600011],
    cnt1[600011], cnt2[600011];
long long ans;
void update(int now) {
  min1[Left[now]] += stop[now];
  min2[Left[now]] += stop[now];
  stop[Left[now]] += stop[now];
  min1[Right[now]] += stop[now];
  min2[Right[now]] += stop[now];
  stop[Right[now]] += stop[now];
  stop[now] = 0;
}
void merge(int now) {
  min1[now] = min1[Left[now]];
  cnt1[now] = cnt1[Left[now]];
  min2[now] = min2[Left[now]];
  cnt2[now] = cnt2[Left[now]];
  if (min1[Right[now]] < min1[now])
    min2[now] = min1[now], cnt2[now] = cnt1[now], min1[now] = min1[Right[now]],
    cnt1[now] = cnt1[Right[now]];
  else if (min1[Right[now]] == min1[now])
    cnt1[now] += cnt1[Right[now]];
  else if (min1[Right[now]] < min2[now])
    min2[now] = min1[Right[now]], cnt2[now] = cnt1[Right[now]];
  else if (min1[Right[now]] == min2[now])
    cnt2[now] += cnt1[Right[now]];
  if (min2[Right[now]] < min2[now])
    min2[now] = min2[Right[now]], cnt2[now] = cnt2[Right[now]];
  else if (min2[Right[now]] == min2[now])
    cnt2[now] += cnt2[Right[now]];
}
void build(int s, int e, int now) {
  if (s == e) {
    min1[now] = f[s];
    cnt1[now] = 1;
    min2[now] = 1 << 29;
    cnt2[now] = 0;
    return;
  }
  int mid = (s + e) / 2;
  Left[now] = ++tot;
  build(s, mid, tot);
  Right[now] = ++tot;
  build(mid + 1, e, tot);
  merge(now);
}
void ins(int p, int s, int e, int l, int r, int now) {
  if (s == l && e == r) {
    min1[now] += p;
    min2[now] += p;
    stop[now] += p;
    return;
  }
  int mid = (l + r) / 2;
  update(now);
  if (e <= mid)
    ins(p, s, e, l, mid, Left[now]);
  else if (s > mid)
    ins(p, s, e, mid + 1, r, Right[now]);
  else
    ins(p, s, mid, l, mid, Left[now]),
        ins(p, mid + 1, e, mid + 1, r, Right[now]);
  merge(now);
}
int find(int x) {
  int l = 1, r = n, now = 0;
  while (l != r) {
    update(now);
    int mid = (l + r) / 2;
    if (x <= mid)
      r = mid, now = Left[now];
    else
      l = mid + 1, now = Right[now];
  }
  return min1[now];
}
int main() {
  scanf("%d", &n);
  for (i = 1; i <= n; i++) scanf("%d", &p[i]), q[p[i]] = i;
  for (i = 1; i <= n; i++) {
    k = 1;
    if (q[i] < n && p[q[i] + 1] < i) k--;
    if (q[i] > 1 && p[q[i] - 1] < i) k--;
    f[i] = f[i - 1] + k;
  }
  f[1] = 1 << 29;
  build(1, n, 0);
  for (i = 1; i < n; i++) {
    if (min1[0] <= 2) ans += cnt1[0];
    if (min2[0] <= 2) ans += cnt2[0];
    if (i < n) {
      int x = p[q[i] - 1], y = p[q[i] + 1];
      if (x > y) swap(x, y);
      if (y < i) ins(-1, i + 1, n, 1, n, 0);
      if (x >= i + 1) {
        if (x > i + 1) ins(-1, i + 1, x - 1, 1, n, 0);
        ins(1, y, n, 1, n, 0);
      } else if (y > i + 1)
        ins(-1, i + 1, y - 1, 1, n, 0);
      ins(1 << 20, i + 1, i + 1, 1, n, 0);
    }
  }
  cout << ans << endl;
  return 0;
}
