#include <bits/stdc++.h>
using namespace std;
const int N(300010), T(1 << 20), INF(99999999);
struct TNode {
  int l, r, min1, min2, cnt1, cnt2, delta;
};
int n;
long long ans;
int p[N], loc[N];
TNode st[T];
void build_tree(int i, int l, int r) {
  st[i].l = l;
  st[i].r = r;
  st[i].min1 = 0;
  st[i].min2 = INF;
  st[i].cnt1 = st[i].cnt2 = r - l + 1;
  st[i].delta = 0;
  if (l != r) {
    int mid = (l + r) / 2;
    build_tree(i * 2, l, mid);
    build_tree(i * 2 + 1, mid + 1, r);
  }
}
void clean(int i) {
  if (st[i].delta == 0) return;
  st[i].min1 += st[i].delta;
  st[i].min2 += st[i].delta;
  if (st[i].l != st[i].r) {
    st[i * 2].delta += st[i].delta;
    st[i * 2 + 1].delta += st[i].delta;
  }
  st[i].delta = 0;
}
TNode operator+(TNode &a, TNode &b) {
  TNode ret;
  ret.l = a.l;
  ret.r = b.r;
  ret.min1 = min(a.min1, b.min1);
  ret.min2 = INF;
  ret.cnt1 = ret.cnt2 = 0;
  ret.delta = 0;
  if (a.min1 > ret.min1) ret.min2 = min(ret.min2, a.min1);
  if (a.min2 > ret.min1) ret.min2 = min(ret.min2, a.min2);
  if (b.min1 > ret.min1) ret.min2 = min(ret.min2, b.min1);
  if (b.min2 > ret.min1) ret.min2 = min(ret.min2, b.min2);
  if (a.min1 == ret.min1) ret.cnt1 += a.cnt1;
  if (b.min1 == ret.min1) ret.cnt1 += b.cnt1;
  if (a.min1 == ret.min2) ret.cnt2 += a.cnt1;
  if (b.min1 == ret.min2) ret.cnt2 += b.cnt1;
  if (a.min2 == ret.min2) ret.cnt2 += a.cnt2;
  if (b.min2 == ret.min2) ret.cnt2 += b.cnt2;
  return ret;
}
void modify(int i, int l, int r, int delta) {
  if (st[i].l == l && st[i].r == r) {
    st[i].delta += delta;
    return;
  }
  clean(i);
  int mid = (st[i].l + st[i].r) / 2;
  if (r <= mid)
    modify(i * 2, l, r, delta);
  else if (mid < l)
    modify(i * 2 + 1, l, r, delta);
  else {
    modify(i * 2, l, mid, delta);
    modify(i * 2 + 1, mid + 1, r, delta);
  }
  clean(i * 2);
  clean(i * 2 + 1);
  st[i] = st[i * 2] + st[i * 2 + 1];
}
int getans(int i, int x) {
  clean(i);
  if (st[i].r <= x) {
    int ret = 0;
    if (st[i].min1 < 3) ret += st[i].cnt1;
    if (st[i].min2 < 3) ret += st[i].cnt2;
    return ret;
  }
  int mid = (st[i].l + st[i].r) / 2;
  if (x <= mid) return getans(i * 2, x);
  return getans(i * 2, mid) + getans(i * 2 + 1, x);
}
int main() {
  cin >> n;
  p[0] = p[n + 1] = INF;
  for (int i = int(1); i < int(n + 1); ++i) {
    cin >> p[i];
    loc[p[i]] = i;
  }
  build_tree(1, 1, n + 1);
  for (int i = int(1); i < int(n + 1); ++i) {
    modify(1, 1, i, 1);
    if (p[loc[i] + 1] < i) modify(1, 1, p[loc[i] + 1], -1);
    if (p[loc[i] - 1] < i) modify(1, 1, p[loc[i] - 1], -1);
    ans += getans(1, i);
  }
  ans -= n;
  cout << ans << endl;
  return 0;
}
