#include <bits/stdc++.h>
using namespace std;
long long read() {
  long long a = 0, x = 1;
  char ch = getchar();
  while (ch > '9' || ch < '0') {
    if (ch == '-') x = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    a = a * 10 + ch - '0';
    ch = getchar();
  }
  return a * x;
}
const long long N = 1e6 + 7, P = 998244353, inf = 1e9 + 7;
long long fpow(long long a, long long x) {
  if (x == 1) return a;
  if (x == 0) return 1;
  long long t = fpow(a, x / 2);
  if (x & 1)
    return t * t % P * a % P;
  else
    return t * t % P;
}
long long n, a[N], pos[N], ans = 0;
long long tre1[N << 2], tre2[N << 2], sum1[N << 2], sum2[N << 2], tag[N << 2];
void push_down(long long root) {
  if (!tag[root]) return;
  tag[root << 1] += tag[root], tag[root << 1 | 1] += tag[root];
  tre1[root << 1] += tag[root], tre2[root << 1] += tag[root];
  tre1[root << 1 | 1] += tag[root], tre2[root << 1 | 1] += tag[root];
  tag[root] = 0;
}
void push_up(long long root) {
  tre1[root] = min(tre1[root << 1], tre1[root << 1 | 1]);
  tre2[root] = min(tre2[root << 1], tre2[root << 1 | 1]);
  if (tre1[root] != tre1[root << 1])
    tre2[root] = min(tre2[root], tre1[root << 1]);
  else if (tre1[root] != tre1[root << 1 | 1])
    tre2[root] = min(tre2[root], tre1[root << 1 | 1]);
  sum1[root] = sum1[root << 1] * (tre1[root << 1] == tre1[root]) +
               sum1[root << 1 | 1] * (tre1[root << 1 | 1] == tre1[root]);
  sum2[root] = sum1[root << 1] * (tre1[root << 1] == tre2[root]) +
               sum1[root << 1 | 1] * (tre1[root << 1 | 1] == tre2[root]);
  sum2[root] += sum2[root << 1] * (tre2[root << 1] == tre2[root]) +
                sum2[root << 1 | 1] * (tre2[root << 1 | 1] == tre2[root]);
}
void modify(long long root, long long l, long long r, long long ql,
            long long qr, long long x) {
  if (l >= ql && r <= qr) {
    tag[root] += x, tre1[root] += x, tre2[root] += x;
    return;
  }
  if (l > qr || r < ql) return;
  push_down(root);
  modify(root << 1, l, (l + r >> 1), ql, qr, x);
  modify(root << 1 | 1, (l + r >> 1) + 1, r, ql, qr, x);
  push_up(root);
}
void build(long long root, long long l, long long r) {
  if (l == r) {
    tre1[root] = 0, sum1[root] = 1, tre2[root] = inf, sum2[root] = 0;
    return;
  }
  build(root << 1, l, (l + r >> 1));
  build(root << 1 | 1, (l + r >> 1) + 1, r);
  push_up(root);
}
long long getans() {
  return sum1[1] * (tre1[1] <= 2) + sum2[1] * (tre2[1] <= 2);
}
void solve() {
  n = read();
  for (long long i = 1; i <= n; i++) pos[a[i] = read()] = i;
  build(1, 1, n);
  modify(1, 1, n, 1, n, inf);
  for (long long i = 1; i <= n; i++) {
    long long maxn = -1, mini = n + 1;
    modify(1, 1, n, i, i, -inf);
    if (pos[i] - 1 > 0)
      maxn = max(maxn, a[pos[i] - 1]), mini = min(mini, a[pos[i] - 1]);
    if (pos[i] + 1 <= n)
      maxn = max(maxn, a[pos[i] + 1]), mini = min(mini, a[pos[i] + 1]);
    if (maxn + 1 <= i) modify(1, 1, n, maxn + 1, i, 1);
    if (mini > i) modify(1, 1, n, 1, i, 1);
    if (maxn > i && mini < i) modify(1, 1, n, mini + 1, i, 1);
    if (maxn <= i && pos[i] != 1 && pos[i] != n)
      modify(1, 1, n, 1, min(mini, i), -1);
    ans += getans() - 1;
  }
  printf("%lld\n", ans);
}
signed main() {
  long long t = 1;
  while (t--) solve();
}
