#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 300000 + 10;
const int INF = 1000000;
struct Node {
  int l, r;
  int addTag;
  int minTag[2], cntTag[2];
  Node *ch[2];
  Node() {}
  Node(int _l, int _r) {
    l = _l;
    r = _r;
    addTag = 0;
    minTag[0] = 0;
    cntTag[0] = r - l;
    minTag[1] = INF;
    cntTag[1] = 0;
    ch[0] = ch[1] = NULL;
  }
  void add(int, int, int);
  Node cnt(int, int);
  void pushDown();
  void update(Node, Node);
  void appAdd(int);
} * root;
Node *buildTree(int l, int r) {
  Node *t = new Node(l, r);
  if (l + 1 == r) return t;
  int mid = l + r >> 1;
  t->ch[0] = buildTree(l, mid);
  t->ch[1] = buildTree(mid, r);
  return t;
}
int N;
int a[MAX_N], b[MAX_N];
void inputData() {
  scanf("%d", &N);
  for (int i = 1; i <= N; ++i) {
    scanf("%d", &a[i]);
    b[a[i]] = i;
  }
  root = buildTree(1, N + 1);
}
void Node::appAdd(int x) {
  addTag += x;
  minTag[0] += x;
  minTag[1] += x;
}
void Node::pushDown() {
  if (addTag && r > l + 1) {
    ch[0]->appAdd(addTag);
    ch[1]->appAdd(addTag);
    addTag = 0;
  }
}
void Node::update(Node p, Node q) {
  for (int i = 0; i < 2; ++i) minTag[i] = INF, cntTag[i] = 0;
  for (int i = 0; i < 2; ++i) {
    if (p.minTag[i] < minTag[0]) {
      minTag[1] = minTag[0];
      minTag[0] = p.minTag[i];
    } else if (p.minTag[i] > minTag[0] && p.minTag[i] < minTag[1]) {
      minTag[1] = p.minTag[i];
    }
    if (q.minTag[i] < minTag[0]) {
      minTag[1] = minTag[0];
      minTag[0] = q.minTag[i];
    } else if (q.minTag[i] > minTag[0] && q.minTag[i] < minTag[1]) {
      minTag[1] = q.minTag[i];
    }
  }
  for (int i = 0; i < 2; ++i)
    for (int j = 0; j < 2; ++j) {
      if (p.minTag[j] == minTag[i]) cntTag[i] += p.cntTag[j];
      if (q.minTag[j] == minTag[i]) cntTag[i] += q.cntTag[j];
    }
}
void Node::add(int _l, int _r, int x) {
  if (_l <= l && _r >= r) {
    appAdd(x);
    return;
  }
  pushDown();
  int mid = l + r >> 1;
  if (_l < mid) ch[0]->add(_l, _r, x);
  if (mid < _r) ch[1]->add(_l, _r, x);
  update(*ch[0], *ch[1]);
}
Node Node::cnt(int _l, int _r) {
  if (_l <= l && _r >= r) {
    return *this;
  }
  pushDown();
  int mid = l + r >> 1;
  if (_r <= mid) return ch[0]->cnt(_l, _r);
  if (_l >= mid) return ch[1]->cnt(_l, _r);
  Node t;
  t.update(ch[0]->cnt(_l, _r), ch[1]->cnt(_l, _r));
  return t;
}
void calcAns() {
  long long ret = 0;
  Node tmp;
  for (int i = 1; i <= N; ++i) {
    root->add(1, i + 1, 1);
    if (b[i] > 1 && a[b[i] - 1] < i) root->add(1, a[b[i] - 1] + 1, -1);
    if (b[i] < N && a[b[i] + 1] < i) root->add(1, a[b[i] + 1] + 1, -1);
    tmp = root->cnt(1, i + 1);
    if (tmp.minTag[0] == 1) ret += tmp.cntTag[0];
    if (tmp.minTag[1] == 2) ret += tmp.cntTag[1];
  }
  cout << ret - N << endl;
}
void solve() {
  inputData();
  calcAns();
}
int main() {
  solve();
  return 0;
}
