#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300000;
int n;
struct Node {
  int l, r;
  int delta;
  int numS, numSC, numB, numBC;
  Node *lChild, *rChild;
} * root, store[MAXN * 2 + 10], *loc = store;
void down(Node* x) {
  if (x->delta) {
    x->numS += x->delta;
    if (x->numB != -1) x->numB += x->delta;
    if (x->lChild) {
      x->lChild->delta += x->delta;
      x->rChild->delta += x->delta;
    }
    x->delta = 0;
  }
}
void up(Node* x) {
  down(x->lChild);
  down(x->rChild);
  static vector<pair<int, int> > tmp;
  tmp.clear();
  tmp.push_back(make_pair(x->lChild->numS, x->lChild->numSC));
  if (x->lChild->numB != -1)
    tmp.push_back(make_pair(x->lChild->numB, x->lChild->numBC));
  tmp.push_back(make_pair(x->rChild->numS, x->rChild->numSC));
  if (x->rChild->numB != -1)
    tmp.push_back(make_pair(x->rChild->numB, x->rChild->numBC));
  x->numS = x->numB = -1;
  sort(tmp.begin(), tmp.end());
  for (int lazy = 0, eager = 0; lazy < tmp.size(); lazy = ++eager) {
    while (eager + 1 < tmp.size() && tmp[eager].first == tmp[eager + 1].first)
      eager++;
    int sum = 0;
    for (int i = (lazy); i <= (eager); i++) sum += tmp[i].second;
    if (x->numS < 0) {
      x->numS = tmp[lazy].first;
      x->numSC = sum;
    } else if (x->numB < 0) {
      x->numB = tmp[lazy].first;
      x->numBC = sum;
    }
  }
}
Node* build(int l, int r) {
  Node* x = loc++;
  x->l = l;
  x->r = r;
  x->delta = 0;
  x->numS = 1;
  x->numSC = r - l + 1;
  x->numB = -1;
  if (l == r) {
    x->lChild = x->rChild = NULL;
  } else {
    int mid = (x->l + x->r) >> 1;
    x->lChild = build(l, mid);
    x->rChild = build(mid + 1, r);
  }
  return x;
}
void init(int n) { root = build(0, n - 1); }
void det(Node* x, int l, int r, int v) {
  down(x);
  if (l <= x->l && x->r <= r)
    x->delta += v;
  else {
    int mid = (x->l + x->r) >> 1;
    if (l <= mid) det(x->lChild, l, r, v);
    if (mid < r) det(x->rChild, l, r, v);
    up(x);
  }
}
int cnt(Node* x, int l, int r) {
  down(x);
  if (l <= x->l && x->r <= r) {
    return (x->numS <= 2 ? x->numSC : 0) +
           (x->numB >= 1 && x->numB <= 2 ? x->numBC : 0);
  } else {
    int mid = (x->l + x->r) >> 1;
    int res = 0;
    if (l <= mid) res += cnt(x->lChild, l, r);
    if (mid < r) res += cnt(x->rChild, l, r);
    return res;
  }
}
void inc(int l, int r) {
  if (l == r + 1) return;
  assert(l <= r);
  ;
  det(root, l, r, 1);
}
void dec(int l, int r) {
  if (l == r + 1) return;
  assert(l <= r);
  ;
  det(root, l, r, -1);
}
int what[MAXN + 10], poss[MAXN + 10];
int* pos = poss + 1;
int main() {
  scanf("%d", &n);
  init(n);
  for (int i = 0; i < (n); i++) {
    scanf("%d", &pos[i]);
    pos[i]--;
    what[pos[i]] = i;
  }
  pos[n] = n;
  pos[-1] = n;
  long long ans = 0;
  for (int i = 0; i < (n); i++) {
    if (i) {
      int pos1 = pos[what[i] - 1], pos2 = pos[what[i] + 1];
      if (pos2 < pos1) swap(pos2, pos1);
      ;
      if (pos2 < i) {
        dec(0, pos1);
        inc(pos2 + 1, i - 1);
      } else if (pos1 < i) {
        inc(pos1 + 1, i - 1);
      } else
        inc(0, i - 1);
    }
    int tmp;
    ans += tmp = cnt(root, 0, i);
    ;
  }
  cout << ans - n << endl;
  return 0;
}
