#include <bits/stdc++.h>
const int maxn = 310000;
const int maxtreetop = 1100000;
const int maxnum = 1000000000;
struct Ttree {
  int start, stop;
  int mark;
  int zx, zxge, zx2, zx2ge;
} tree[maxtreetop + 1];
long long result = 0;
int n;
int wz[maxn + 1], a[maxn + 1];
void init() {
  int i;
  scanf("%d", &n);
  for (i = 1; i <= n; ++i) {
    scanf("%d", &wz[i]);
    a[wz[i]] = i;
  }
}
void jia(int &a, int delta) {
  if (a <= n) a += delta;
}
void putdown(int p) {
  if (tree[p].start < tree[p].stop) {
    tree[p * 2].mark += tree[p].mark;
    jia(tree[p * 2].zx, tree[p].mark);
    jia(tree[p * 2].zx2, tree[p].mark);
    tree[p * 2 + 1].mark += tree[p].mark;
    jia(tree[p * 2 + 1].zx, tree[p].mark);
    jia(tree[p * 2 + 1].zx2, tree[p].mark);
  }
  tree[p].mark = 0;
}
void update(int p) {
  struct Tpair {
    int num, ge;
  } a[5];
  a[1].num = tree[p * 2].zx;
  a[1].ge = tree[p * 2].zxge;
  a[2].num = tree[p * 2].zx2;
  a[2].ge = tree[p * 2].zx2ge;
  a[3].num = tree[p * 2 + 1].zx;
  a[3].ge = tree[p * 2 + 1].zxge;
  a[4].num = tree[p * 2 + 1].zx2;
  a[4].ge = tree[p * 2 + 1].zx2ge;
  int i, j;
  Tpair k;
  for (i = 2; i <= 4; ++i) {
    j = i - 1;
    k = a[i];
    while ((j >= 1) && (k.num < a[j].num)) {
      a[j + 1] = a[j];
      --j;
    }
    a[j + 1] = k;
  }
  j = 1;
  for (i = 2; i <= 4; ++i)
    if (a[i].num == a[j].num)
      a[j].ge += a[i].ge;
    else
      a[++j] = a[i];
  tree[p].zx = a[1].num;
  tree[p].zxge = a[1].ge;
  tree[p].zx2 = a[2].num;
  tree[p].zx2ge = a[2].ge;
}
void init_tree(int p, int left, int right) {
  tree[p].start = left;
  tree[p].stop = right;
  tree[p].zx = maxnum;
  tree[p].zx2 = maxnum + 1;
  tree[p].zxge = tree[p].zx2ge = 0;
  tree[p].mark = 0;
  if (tree[p].start < tree[p].stop) {
    int mid = (left + right) / 2;
    init_tree(p * 2, left, mid);
    init_tree(p * 2 + 1, mid + 1, right);
  }
}
void ins_tree(int p, int x, int num) {
  putdown(p);
  if (tree[p].start == tree[p].stop) {
    tree[p].zx = num;
    tree[p].zxge = 1;
    return;
  }
  int mid = (tree[p].start + tree[p].stop) / 2;
  if (x <= mid)
    ins_tree(p * 2, x, num);
  else
    ins_tree(p * 2 + 1, x, num);
  update(p);
}
void seg_tree(int p, int left, int right, int mark) {
  if (left > right) return;
  putdown(p);
  if ((left <= tree[p].start) && (right >= tree[p].stop)) {
    jia(tree[p].zx, mark);
    jia(tree[p].zx2, mark);
    tree[p].mark += mark;
    return;
  }
  int mid = (tree[p].start + tree[p].stop) / 2;
  if (left <= mid) seg_tree(p * 2, left, right, mark);
  if (right > mid) seg_tree(p * 2 + 1, left, right, mark);
  update(p);
}
void work() {
  int i, j, k, t1, t2;
  init_tree(1, 1, n);
  ins_tree(1, n, 1);
  result = 1;
  for (i = n - 1; i >= 1; --i) {
    t1 = t2 = n + 1;
    if ((a[i] > 1) && (wz[a[i] - 1] > i)) t1 = wz[a[i] - 1];
    if ((a[i] < n) && (wz[a[i] + 1] > i)) t2 = wz[a[i] + 1];
    if (t1 > t2) {
      j = t1;
      t1 = t2;
      t2 = j;
    }
    seg_tree(1, i + 1, t1 - 1, 1);
    seg_tree(1, t2, n, -1);
    ins_tree(1, i, 1);
    if ((tree[1].zx == 1) || (tree[1].zx == 2)) result += tree[1].zxge;
    if ((tree[1].zx2 == 1) || (tree[1].zx2 == 2)) result += tree[1].zx2ge;
  }
  result -= n;
}
void output() { printf("%I64d\n", result); }
int main() {
  init();
  work();
  output();
  return 0;
}
