#include <bits/stdc++.h>
long long int ans;
int n;
int p[1000000], inv[1000000], mark[2000000], s[2000000], cnt1[2000000],
    cnt2[2000000];
void build(int l, int r) {
  cnt1[(l + r) | (l != r)] = r - l + 1;
  if (l == r) return;
  int mid = (l + r) >> 1;
  build(l, mid);
  build(mid + 1, r);
}
void pass(int l, int r) {
  int mid = (l + r) >> 1;
  int num = (l + r) | (l != r);
  int left = (l + mid) | (l != mid);
  int right = (mid + 1 + r) | (mid + 1 != r);
  if (mark[num]) {
    mark[left] += mark[num];
    s[left] += mark[num];
    mark[right] += mark[num];
    s[right] += mark[num];
    mark[num] = 0;
  }
}
void update(int l, int r) {
  int mid = (l + r) >> 1;
  int num = (l + r) | (l != r);
  int left = (l + mid) | (l != mid);
  int right = (mid + 1 + r) | (mid + 1 != r);
  s[num] = std::min(s[left], s[right]);
  cnt1[num] =
      cnt1[left] * (s[left] == s[num]) + cnt1[right] * (s[right] == s[num]);
  cnt2[num] =
      cnt2[left] * (s[left] == s[num]) + cnt2[right] * (s[right] == s[num]);
  cnt2[num] += cnt1[left] * (s[left] == s[num] + 1);
  cnt2[num] += cnt1[right] * (s[num] + 1 == s[right]);
}
void add(int l, int r, int ll, int rr, int d) {
  if (l == ll && r == rr) {
    mark[(l + r) | (l != r)] += d;
    s[(l + r) | (l != r)] += d;
    return;
  }
  pass(l, r);
  int mid = (l + r) >> 1;
  if (ll > mid)
    add(mid + 1, r, ll, rr, d);
  else if (rr <= mid)
    add(l, mid, ll, rr, d);
  else
    add(l, mid, ll, mid, d), add(mid + 1, r, mid + 1, rr, d);
  update(l, r);
}
long long int query(int l, int r, int ll, int rr) {
  int mid = (l + r) >> 1;
  int num = (l + r) | (l != r);
  if (l == ll && r == rr) {
    return cnt1[num] * (s[num] <= 2) + cnt2[num] * (s[num] == 1);
  }
  if (ll > mid)
    return query(mid + 1, r, ll, rr);
  else if (rr <= mid)
    return query(l, mid, ll, rr);
  return query(l, mid, ll, mid) + query(mid + 1, r, mid + 1, rr);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &p[i]), inv[p[i]] = i;
  build(1, n);
  for (int l = n; l; l--) {
    int x1 = p[inv[l] + 1];
    int x2 = p[inv[l] - 1];
    if (x1 > x2) {
      int tmp = x2;
      x2 = x1;
      x1 = tmp;
    }
    if (x2 < l)
      add(1, n, l, n, 1);
    else if (x1 < l)
      add(1, n, l, x2 - 1, 1);
    else
      add(1, n, l, x1 - 1, 1), add(1, n, x2, n, -1);
    ans += query(1, n, l, n);
  }
  std::cout << ans - n;
}
