#include <bits/stdc++.h>
int mn[1200005], lazy[1200005], cnt[1200005], sec[1200005];
int arr[300005], pos[300005];
inline void paint(int u, int x) {
  mn[u] += x;
  lazy[u] += x;
}
inline void push_up(int u) {
  mn[u] = std::min(mn[u << 1], mn[u << 1 | 1]);
  cnt[u] = cnt[u << 1] * (mn[u << 1] == mn[u]) +
           cnt[u << 1 | 1] * (mn[u << 1 | 1] == mn[u]);
  sec[u] = sec[u << 1] * (mn[u << 1] == mn[u]) +
           sec[u << 1 | 1] * (mn[u << 1 | 1] == mn[u]) +
           cnt[u << 1] * (mn[u << 1] == mn[u] + 1) +
           cnt[u << 1 | 1] * (mn[u << 1 | 1] == mn[u] + 1);
}
inline void push_down(int u) {
  if (!lazy[u]) return;
  paint(u << 1, lazy[u]);
  paint(u << 1 | 1, lazy[u]);
  lazy[u] = 0;
}
void modify(int u, int l, int r, int L, int R, int x) {
  if (L <= l && r <= R) {
    paint(u, x);
    return;
  }
  push_down(u);
  int m = l + r >> 1;
  if (L <= m) modify(u << 1, l, m, L, R, x);
  if (m < R) modify(u << 1 | 1, m + 1, r, L, R, x);
  push_up(u);
}
long long query(int u, int l, int r, int L, int R) {
  fflush(stdout);
  if (L <= l && r <= R) return sec[u] * (mn[u] <= 1) + cnt[u] * (mn[u] <= 2);
  push_down(u);
  int m = l + r >> 1;
  long long res = 0;
  if (L <= m) res += query(u << 1, l, m, L, R);
  if (m < R) res += query(u << 1 | 1, m + 1, r, L, R);
  return res;
}
void build(int u, int l, int r) {
  if (l == r) {
    cnt[u] = 1;
    return;
  }
  int m = l + r >> 1;
  build(u << 1, l, m);
  build(u << 1 | 1, m + 1, r);
  push_up(u);
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", arr + i);
    pos[arr[i]] = i;
  }
  build(1, 1, n);
  long long ans = 0;
  for (int i = 1; i <= n; i++) {
    int x = arr[pos[i] - 1], y = arr[pos[i] + 1];
    modify(1, 1, n, 1, i, 1);
    if (x && x < i) modify(1, 1, n, 1, x, -1);
    if (y && y < i) modify(1, 1, n, 1, y, -1);
    if (i != 1) ans += query(1, 1, n, 1, i - 1);
  }
  printf("%lld\n", ans);
  return 0;
}
