#include <bits/stdc++.h>
using namespace std;
const int maxn = 300010, inf = 0x7ffffff;
int n, a[maxn], pos[maxn], sum1[maxn << 2], sum2[maxn << 2], min1[maxn << 2],
    tag[maxn << 2], min2[maxn << 2];
long long ans;
void solve(int o, int v, int c) {
  if (v < min1[o]) {
    min2[o] = min1[o];
    sum2[o] = sum1[o];
    min1[o] = v;
    sum1[o] = c;
  } else if (v == min1[o])
    sum1[o] += c;
  else if (v < min2[o]) {
    min2[o] = v;
    sum2[o] = c;
  } else if (v == min2[o])
    sum2[o] += c;
}
void pushup(int o) {
  sum1[o] = sum1[o * 2];
  min1[o] = min1[o * 2];
  sum2[o] = sum2[o * 2];
  min2[o] = min2[o * 2];
  solve(o, min2[o * 2 + 1], sum2[o * 2 + 1]);
  solve(o, min1[o * 2 + 1], sum1[o * 2 + 1]);
}
void pushdown(int o) {
  if (tag[o]) {
    tag[o * 2] += tag[o];
    tag[o * 2 + 1] += tag[o];
    min1[o * 2] += tag[o];
    min1[o * 2 + 1] += tag[o];
    min2[o * 2] += tag[o];
    min2[o * 2 + 1] += tag[o];
    tag[o] = 0;
  }
}
void build(int o, int l, int r) {
  min1[o] = 0;
  sum1[o] = (r - l + 1);
  min2[o] = inf;
  sum2[o] = 0;
  if (l == r) return;
  int mid = (l + r) >> 1;
  build(o * 2, l, mid);
  build(o * 2 + 1, mid + 1, r);
  pushup(o);
}
void update(int o, int l, int r, int x, int y, int v) {
  if (x <= l && r <= y) {
    min1[o] += v;
    min2[o] += v;
    tag[o] += v;
    return;
  }
  pushdown(o);
  int mid = (l + r) >> 1;
  if (x <= mid) update(o * 2, l, mid, x, y, v);
  if (y > mid) update(o * 2 + 1, mid + 1, r, x, y, v);
  pushup(o);
}
void query(int o, int l, int r, int x, int y) {
  if (x <= l && r <= y) {
    if (min1[o] <= 2) ans += sum1[o];
    if (min2[o] <= 2) ans += sum2[o];
    return;
  }
  pushdown(o);
  int mid = (l + r) >> 1;
  if (x <= mid) query(o * 2, l, mid, x, y);
  if (y > mid) query(o * 2 + 1, mid + 1, r, x, y);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    pos[a[i]] = i;
  }
  build(1, 1, n);
  for (int i = 1; i <= n; i++) {
    int l = -1, r = -1;
    if (pos[i] > 1 && i >= a[pos[i] - 1]) l = a[pos[i] - 1];
    if (pos[i] < n && i >= a[pos[i] + 1]) r = a[pos[i] + 1];
    if (l > r) swap(l, r);
    if (r == -1)
      update(1, 1, n, 1, i, 1);
    else if (l == -1)
      update(1, 1, n, r + 1, i, 1);
    else {
      update(1, 1, n, r + 1, i, 1);
      update(1, 1, n, 1, l, -1);
    }
    query(1, 1, n, 1, i);
  }
  cout << ans - n << endl;
  return 0;
}
