#include <bits/stdc++.h>
using namespace std;
const int inf = 1 << 30, N = 310000;
int n;
int a[N], b[N];
int SA[N << 2], SB[N << 2], A[N << 2], B[N << 2], l[N << 2], r[N << 2],
    add[N << 2];
void build(const int x, const int y, const int z) {
  l[z] = x, r[z] = y, A[z] = 0, B[z] = inf, SA[z] = y - x + 1,
  SB[z] = add[z] = 0;
  if (x == y) return;
  int mid = (x + y) >> 1;
  build(x, mid, z << 1), build(mid + 1, y, (z << 1) + 1);
}
void push(const int z) {
  if (add[z] == 0) return;
  A[z] += add[z], B[z] += add[z];
  if (l[z] != r[z]) {
    int K = z << 1;
    add[K] += add[z], add[K + 1] += add[z];
  }
  add[z] = 0;
}
void change(const int x, const int y, const int z, const int D) {
  if (l[z] == x && r[z] == y) {
    add[z] += D;
    return;
  }
  int mid = (l[z] + r[z]) >> 1, K = z << 1;
  if (y <= mid)
    change(x, y, K, D);
  else if (x > mid)
    change(x, y, K + 1, D);
  else
    change(x, mid, K, D), change(mid + 1, y, K + 1, D);
  push(z), push(K), push(K + 1);
  A[z] = min(A[K], A[K + 1]), B[z] = inf, SA[z] = SB[z] = 0;
  if (B[K] > A[z] && B[K] < B[z]) B[z] = B[K];
  if (A[K] > A[z] && A[K] < B[z]) B[z] = A[K];
  if (B[K + 1] > A[z] && B[K + 1] < B[z]) B[z] = B[K + 1];
  if (A[K + 1] > A[z] && A[K + 1] < B[z]) B[z] = A[K + 1];
  if (A[K] == A[z]) SA[z] += SA[K];
  if (A[K + 1] == A[z]) SA[z] += SA[K + 1];
  if (A[K] == B[z]) SB[z] += SA[K];
  if (B[K] == B[z]) SB[z] += SB[K];
  if (A[K + 1] == B[z]) SB[z] += SA[K + 1];
  if (B[K + 1] == B[z]) SB[z] += SB[K + 1];
}
int Gans(const int y, const int z) {
  push(z);
  if (r[z] <= y) {
    int p = 0;
    if (A[z] <= 2) p += SA[z];
    if (B[z] <= 2) p += SB[z];
    return p;
  }
  int mid = (l[z] + r[z]) >> 1, K = z << 1;
  if (y <= mid) return Gans(y, K);
  return Gans(y, K) + Gans(y, K + 1);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), b[a[i]] = i;
  build(1, n, 1);
  a[0] = a[n + 1] = 0;
  for (int i = 1; i <= n; ++i) {
    if (a[b[i] - 1] > i && a[b[i] + 1] > i)
      change(1, i, 1, -1);
    else if (a[b[i] - 1] < i && a[b[i] + 1] < i)
      change(1, i, 1, 1);
  }
  long long ans = 0;
  a[0] = a[n + 1] = inf;
  for (int i = n; i > 1; --i) {
    ans += Gans(i - 1, 1);
    change(1, i, 1, -1);
    if (a[b[i] - 1] < i) change(1, a[b[i] - 1], 1, 1);
    if (a[b[i] + 1] < i) change(1, a[b[i] + 1], 1, 1);
  }
  cout << ans << endl;
  return 0;
}
