#include <bits/stdc++.h>
using namespace std;
template <typename T>
bool checkmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
bool checkmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
const int maxn = 3e5 + 100;
struct Tree {
  int add;
  int num1, num2;
  int val1, val2;
  Tree() {
    add = num1 = num2 = 0;
    val1 = val2 = 0;
  }
} T[maxn * 5];
int a[maxn], b[maxn];
const int INF = 1e9 + 10;
void Pushdown(int rt, int l, int r) {
  if (T[rt].add) {
    if (l != r) {
      T[(rt << 1)].add += T[rt].add;
      T[(rt << 1 | 1)].add += T[rt].add;
      T[rt].val1 += T[rt].add;
      T[rt].val2 += T[rt].add;
      if (T[rt].val2 > INF) T[rt].val2 = INF;
    } else {
      T[rt].val1 += T[rt].add;
      T[rt].num1 = 1;
      T[rt].val2 = INF;
      T[rt].num2 = 0;
    }
    T[rt].add = 0;
  }
}
struct Pair {
  int val, num;
};
bool cmp(Pair L, Pair R) { return L.val < R.val; }
void PushUp(int rt, int l, int r) {
  if (l == r) return;
  Pushdown((rt << 1), l, ((l + r) >> 1));
  Pushdown((rt << 1 | 1), ((l + r) >> 1) + 1, r);
  Pair p[4];
  p[0].val = T[(rt << 1)].val1, p[0].num = T[(rt << 1)].num1;
  p[1].val = T[(rt << 1)].val2, p[1].num = T[(rt << 1)].num2;
  p[2].val = T[(rt << 1 | 1)].val1, p[2].num = T[(rt << 1 | 1)].num1;
  p[3].val = T[(rt << 1 | 1)].val2, p[3].num = T[(rt << 1 | 1)].num2;
  sort(p, p + 4, cmp);
  int i, n = 4;
  for (i = 0; i < n - 1; i++) {
    while (i < n - 1 && p[i + 1].val == p[i].val) {
      p[i].num += p[i + 1].num;
      for (int j = i + 1; j < n - 1; j++) {
        p[j] = p[j + 1];
      }
      n--;
    }
  }
  if (n >= 2) {
    T[rt].val1 = p[0].val;
    T[rt].num1 = p[0].num;
    T[rt].val2 = p[1].val;
    T[rt].num2 = p[1].num;
  } else {
    T[rt].val1 = p[0].val;
    T[rt].num1 = p[0].num;
    T[rt].val2 = INF;
    T[rt].num2 = 0;
  }
}
void add(int rt, int l, int r, int L, int R, int val) {
  if (L > R) return;
  Pushdown(rt, l, r);
  if (l == L && r == R) {
    T[rt].add += val;
    return;
  }
  if (R <= ((l + r) >> 1))
    add((rt << 1), l, ((l + r) >> 1), L, R, val);
  else if (L > ((l + r) >> 1))
    add((rt << 1 | 1), ((l + r) >> 1) + 1, r, L, R, val);
  else
    add((rt << 1), l, ((l + r) >> 1), L, ((l + r) >> 1), val),
        add((rt << 1 | 1), ((l + r) >> 1) + 1, r, ((l + r) >> 1) + 1, R, val);
  PushUp(rt, l, r);
}
int query(int rt, int l, int r, int L, int R) {
  if (L > R) return 0;
  Pushdown(rt, l, r);
  if (l == L && r == R)
    return T[rt].num1 * (T[rt].val1 <= 2 ? 1 : 0) +
           T[rt].num2 * (T[rt].val2 <= 2 ? 1 : 0);
  if (R <= ((l + r) >> 1))
    return query((rt << 1), l, ((l + r) >> 1), L, R);
  else if (L > ((l + r) >> 1))
    return query((rt << 1 | 1), ((l + r) >> 1) + 1, r, L, R);
  else
    return query((rt << 1), l, ((l + r) >> 1), L, ((l + r) >> 1)) +
           query((rt << 1 | 1), ((l + r) >> 1) + 1, r, ((l + r) >> 1) + 1, R);
}
void Build(int rt, int l, int r) {
  if (l == r) {
    T[rt].val1 = 1;
    T[rt].num1 = 1;
    T[rt].val2 = INF;
    T[rt].num2 = 0;
    return;
  }
  Build((rt << 1), l, ((l + r) >> 1));
  Build((rt << 1 | 1), ((l + r) >> 1) + 1, r);
  PushUp(rt, l, r);
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]), b[a[i]] = i;
  Build(1, 1, n);
  long long ans = 0;
  for (int i = 1; i <= n; i++) {
    int L = a[b[i] + 1], R = a[b[i] - 1];
    if (L > R) swap(L, R);
    if (R < i) add(1, 1, n, R + 1, i - 1, 1);
    if (L < i && R > i) add(1, 1, n, L + 1, i - 1, 1);
    if (L && L < i && R < i) add(1, 1, n, 1, L, -1);
    if (L > i && R > i) add(1, 1, n, 1, i - 1, 1);
    ans += query(1, 1, n, 1, i - 1);
  }
  cout << ans << endl;
  return 0;
}
