#include <bits/stdc++.h>
using namespace std;
int n, m, sz;
int a[333333], pos[333333];
int tot;
long long int res;
int num[333333];
int stat[333333];
int minVal[666], buf[666];
void push(int id) {
  for (int i = id * sz; i < min((id + 1) * sz, n); i++) {
    num[i] += buf[id];
  }
  buf[id] = 0;
  if (minVal[id] <= 1) tot -= stat[id * sz + 1 - minVal[id]];
  if (minVal[id] <= 2) tot -= stat[id * sz + 2 - minVal[id]];
}
void update(int id) {
  int& w = minVal[id];
  w = n;
  for (int i = id * sz; i < min((id + 1) * sz, n); i++) {
    if (num[i] < w) w = num[i];
    stat[i] = 0;
  }
  for (int i = id * sz; i < min((id + 1) * sz, n); i++)
    stat[id * sz + num[i] - w]++;
  if (minVal[id] <= 1) tot += stat[id * sz + 1 - minVal[id]];
  if (minVal[id] <= 2) tot += stat[id * sz + 2 - minVal[id]];
}
void add(int s, int e, int x) {
  ++e;
  if (s >= e) return;
  int is = s / sz, ie = e / sz;
  if (is == ie) {
    push(is);
    for (int i = s; i < e; i++) num[i] += x;
    update(is);
  } else {
    push(is);
    for (int i = s; i < min(n, (is + 1) * sz); i++) num[i] += x;
    update(is);
    push(ie);
    for (int i = ie * sz; i < e; i++) num[i] += x;
    update(ie);
    for (int i = is + 1; i < ie; i++) {
      if (minVal[i] <= 1) tot -= stat[i * sz + 1 - minVal[i]];
      if (minVal[i] <= 2) tot -= stat[i * sz + 2 - minVal[i]];
      buf[i] += x;
      minVal[i] += x;
      if (minVal[i] <= 1) tot += stat[i * sz + 1 - minVal[i]];
      if (minVal[i] <= 2) tot += stat[i * sz + 2 - minVal[i]];
    }
  }
}
int main() {
  scanf("%d", &n);
  if (n <= 2) {
    printf("%d\n", n - 1);
    return 0;
  }
  for (int i = 0; i < n; i++) {
    scanf("%d", &pos[i]);
    --pos[i];
    a[pos[i]] = i;
    num[i] = 0;
  }
  tot = 0;
  sz = max((int)sqrt(n + .5), 3);
  m = (n - 1) / sz + 1;
  for (int i = 0; i < m; i++) {
    minVal[i] = 0;
    stat[i * sz] = min(n, (i + 1) * sz) - (i * sz);
  }
  for (int i = 0; i < n; i++) {
    int x = a[i] == 0 ? -1 : pos[a[i] - 1],
        y = a[i] == n - 1 ? -1 : pos[a[i] + 1];
    if (x > i) x = -1;
    if (y > i) y = -1;
    if (x > y) swap(x, y);
    add(0, x, -1);
    add(y + 1, i, 1);
    res += tot;
  }
  printf("%I64d\n", res - n);
  return 0;
}
