#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0;
  char ch = getchar();
  bool positive = 1;
  for (; ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-') positive = 0;
  for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
  return positive ? x : -x;
}
const int N = 300005;
int n, ll, rr, A, a[N], b[N], d[N << 2], m[N << 2], f[N << 2], s[N << 2];
long long ans;
void update(int t) {
  int L = t * 2, R = L + 1;
  m[t] = m[L] < m[R] ? m[L] : m[R];
  f[t] = f[L] * (m[t] == m[L]) + f[R] * (m[t] == m[R]);
  s[t] = s[L] * (m[t] == m[L]) + s[R] * (m[t] == m[R]) +
         f[L] * (m[t] + 1 == m[L]) + f[R] * (m[t] + 1 == m[R]);
}
void build(int t, int l, int r) {
  if (l == r)
    f[t] = r - l + 1;
  else {
    int mid = l + r >> 1;
    build(t * 2, l, mid), build(t * 2 + 1, mid + 1, r);
  }
}
void down(int t, int A) {
  d[t] = 0, d[t * 2] += A, d[t * 2 + 1] += A;
  m[t * 2] += A, m[t * 2 + 1] += A;
}
void add(int t, int l, int r, int A) {
  if (l > rr || r < ll) return;
  if (ll <= l && r <= rr) {
    m[t] += A, d[t] += A;
    return;
  }
  int mid = l + r >> 1;
  if (d[t]) down(t, d[t]);
  add(t * 2, l, mid, A), add(t * 2 + 1, mid + 1, r, A), update(t);
}
int query(int t, int l, int r, int x) {
  if (l > x) return 0;
  if (r <= x) return s[t] * (m[t] <= 1) + f[t] * (m[t] <= 2);
  int mid = l + r >> 1;
  if (d[t]) down(t, d[t]);
  return query(t * 2, l, mid, x) + query(t * 2 + 1, mid + 1, r, x);
}
int main() {
  n = read();
  build(1, 1, n);
  for (int i = 1; i <= n; i++) a[i] = read(), b[a[i]] = i;
  for (int i = 1; i <= n; i++) {
    int x = a[b[i] - 1], y = a[b[i] + 1];
    ll = 1, rr = i, add(1, 1, n, 1);
    if (x && x < i) ll = 1, rr = x, add(1, 1, n, -1);
    if (y && y < i) ll = 1, rr = y, add(1, 1, n, -1);
    ans += query(1, 1, n, i - 1);
  }
  cout << ans << endl;
  return 0;
}
