#include <bits/stdc++.h>
using namespace std;
const int inf = 1000000000;
struct tree {
  int d1, d2, s1, s2, lnum, rnum, delta;
  tree* lch;
  tree* rch;
};
int a[300010], f[300010];
void build(tree* x, int l, int r) {
  x->d1 = inf;
  x->d2 = 2 * inf;
  x->s1 = r - l + 1;
  x->s2 = 0;
  x->lnum = l;
  x->rnum = r;
  x->delta = 0;
  if (l == r) return;
  int mid = (l + r) >> 1;
  x->lch = new tree;
  build(x->lch, l, mid);
  x->rch = new tree;
  build(x->rch, mid + 1, r);
}
void newd(tree* x, int d, int s) {
  if (x->d1 > d) {
    x->d2 = x->d1;
    x->s2 = x->s1;
    x->d1 = d;
    x->s1 = s;
  } else {
    if (x->d1 == d)
      x->s1 += s;
    else {
      if (x->d2 > d) {
        x->d2 = d;
        x->s2 = s;
      } else if (x->d2 == d)
        x->s2 += s;
    }
  }
}
void pushdown(tree* x) {
  if (x->delta) {
    x->lch->d1 += x->delta;
    x->lch->d2 += x->delta;
    x->lch->delta += x->delta;
    x->rch->d1 += x->delta;
    x->rch->d2 += x->delta;
    x->rch->delta += x->delta;
    x->delta = 0;
  }
}
void pushup(tree* x) {
  x->d1 = x->lch->d1;
  x->s1 = x->lch->s1;
  x->d2 = x->lch->d2;
  x->s2 = x->lch->s2;
  newd(x, x->rch->d1, x->rch->s1);
  newd(x, x->rch->d2, x->rch->s2);
}
void change(tree* x, int l, int r, int k) {
  if ((l <= x->lnum) && (r >= x->rnum)) {
    x->d1 += k;
    x->d2 += k;
    x->delta += k;
    return;
  }
  pushdown(x);
  if (l < x->rch->lnum) change(x->lch, l, r, k);
  if (r > x->lch->rnum) change(x->rch, l, r, k);
  pushup(x);
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i <= n; i++) f[a[i]] = i;
  tree* root = new tree;
  build(root, 1, n);
  long long ans = 0;
  for (int i = n; i; i--) {
    change(root, i, i, -inf);
    change(root, i, n, 1);
    if ((f[i] > 1) && (a[f[i] - 1] > i)) change(root, a[f[i] - 1], n, -1);
    if ((f[i] < n) && (a[f[i] + 1] > i)) change(root, a[f[i] + 1], n, -1);
    if (root->d1 <= 2) ans += root->s1;
    if (root->d2 <= 2) ans += root->s2;
  }
  printf("%I64d\n", ans - n);
  return 0;
}
