#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = (x << 1) + (x << 3) + ch - '0';
    ch = getchar();
  }
  return x * f;
}
const long long maxn = 4e5 + 1e2;
struct Node {
  long long mn, cimn;
  long long sum1, sum2;
};
Node f[4 * maxn];
long long add[4 * maxn];
long long n, m;
long long a[maxn], b[maxn];
long long ans;
void up(long long root) {
  if (f[2 * root].mn < f[2 * root + 1].mn) {
    f[root].mn = f[2 * root].mn;
    f[root].cimn = min(f[2 * root].cimn, f[2 * root + 1].mn);
  } else {
    if (f[2 * root].mn > f[2 * root + 1].mn) {
      f[root].mn = f[2 * root + 1].mn;
      f[root].cimn = min(f[2 * root].mn, f[2 * root + 1].cimn);
    } else {
      f[root].mn = min(f[2 * root].mn, f[2 * root + 1].mn);
      f[root].cimn = min(f[2 * root].cimn, f[2 * root + 1].cimn);
    }
  }
  if (f[root].cimn == f[root].mn) f[root].cimn = 1e9;
  f[root].sum1 = f[2 * root].sum1 * (f[2 * root].mn == f[root].mn) +
                 f[2 * root + 1].sum1 * (f[2 * root + 1].mn == f[root].mn);
  f[root].sum2 = f[2 * root].sum2 * (f[2 * root].cimn == f[root].cimn) +
                 f[2 * root + 1].sum2 * (f[2 * root + 1].cimn == f[root].cimn &&
                                         f[root].cimn != 1e9);
  f[root].sum2 += f[2 * root].sum1 * (f[2 * root].mn == f[root].cimn) +
                  f[2 * root + 1].sum1 * (f[2 * root + 1].mn == f[root].cimn);
}
void pushdown(long long root, long long l, long long r) {
  if (add[root]) {
    add[2 * root] += add[root];
    add[2 * root + 1] += add[root];
    f[2 * root].mn += add[root];
    f[2 * root].cimn += add[root];
    f[2 * root + 1].mn += add[root];
    f[2 * root + 1].cimn += add[root];
    add[root] = 0;
  }
}
void build(long long root, long long l, long long r) {
  if (l == r) {
    f[root].sum1 = 1;
    f[root].sum2 = 0;
    f[root].cimn = 1e9;
    return;
  }
  long long mid = l + r >> 1;
  build(2 * root, l, mid);
  build(2 * root + 1, mid + 1, r);
  up(root);
}
void update(long long root, long long l, long long r, long long x, long long y,
            long long p) {
  if (x <= l && r <= y) {
    add[root] += p;
    f[root].mn += p;
    f[root].cimn += p;
    return;
  }
  long long mid = l + r >> 1;
  pushdown(root, l, r);
  if (x <= mid) update(2 * root, l, mid, x, y, p);
  if (y > mid) update(2 * root + 1, mid + 1, r, x, y, p);
  up(root);
}
long long query(long long root, long long l, long long r, long long x,
                long long y) {
  if (x <= l && r <= y) {
    return f[root].sum1 * (f[root].mn <= 2) +
           f[root].sum2 * (f[root].cimn != f[root].mn && f[root].cimn <= 2);
  }
  long long mid = l + r >> 1;
  long long ans = 0;
  pushdown(root, l, r);
  if (x <= mid) ans = ans + query(2 * root, l, mid, x, y);
  if (y > mid) ans = ans + query(2 * root + 1, mid + 1, r, x, y);
  return ans;
}
signed main() {
  n = read();
  for (long long i = 1; i <= n; i++) a[i] = read();
  for (long long i = 1; i <= n; i++) b[a[i]] = i;
  build(1, 1, n);
  for (long long i = 1; i <= n; i++) {
    long long x = a[b[i] - 1], y = a[b[i] + 1];
    update(1, 1, n, 1, i, 1);
    if (x && x < i) update(1, 1, n, 1, x, -1);
    if (y && y < i) update(1, 1, n, 1, y, -1);
    ans = ans + query(1, 1, n, 1, i);
  }
  cout << ans - n << endl;
  return 0;
}
