#include <bits/stdc++.h>
using namespace std;
int read() {
  char ch = getchar();
  int num = 0;
  while (ch < '0' || '9' < ch) ch = getchar();
  while ('0' <= ch && ch <= '9') {
    num = num * 10 + ch - '0';
    ch = getchar();
  }
  return num;
}
const int MAXN = 3e5 + 2;
int N, a[MAXN], pos[MAXN];
long long Ans;
bool vis[MAXN];
int min1[MAXN << 2], min2[MAXN << 2], cnt1[MAXN << 2], cnt2[MAXN << 2],
    tag[MAXN << 2];
const int MAXX = 0x3f3f3f3f;
void buildTree(int L, int R, int x) {
  cnt1[x] = R - L + 1;
  min2[x] = MAXX;
  if (L == R) return;
  int mid = (L + R) >> 1;
  buildTree(L, mid, x << 1);
  buildTree(mid + 1, R, (x << 1) | 1);
}
void down(int x) {
  min1[x << 1] += tag[x];
  min1[(x << 1) | 1] += tag[x];
  min2[x << 1] += tag[x];
  min2[(x << 1) | 1] += tag[x];
  tag[x << 1] += tag[x];
  tag[(x << 1) | 1] += tag[x];
  tag[x] = 0;
}
void upd(int x) {
  int p = min1[x << 1], q = min1[(x << 1) | 1], r = min2[x << 1],
      s = min2[(x << 1) | 1];
  min1[x] = min(p, q);
  cnt1[x] = (min1[x] == p ? cnt1[x << 1] : 0) +
            (min1[x] == q ? cnt1[(x << 1) | 1] : 0);
  min2[x] = min(r, s);
  if (p != q) min2[x] = min(min2[x], max(p, q));
  cnt2[x] = (min2[x] == p ? cnt1[x << 1] : 0) +
            (min2[x] == q ? cnt1[(x << 1) | 1] : 0) +
            (min2[x] == r ? cnt2[x << 1] : 0) +
            (min2[x] == s ? cnt2[(x << 1) | 1] : 0);
}
void update(int L, int R, int x, int l, int r, int val) {
  if (R < l || r < L) return;
  if (l <= L && R <= r) {
    min1[x] += val;
    min2[x] += val;
    tag[x] += val;
    return;
  }
  int mid = (L + R) >> 1;
  if (tag[x]) down(x);
  update(L, mid, x << 1, l, r, val);
  update(mid + 1, R, (x << 1) | 1, l, r, val);
  upd(x);
}
int query(int L, int R, int x, int l, int r) {
  if (R < l || r < L) return 0;
  if (l <= L && R <= r)
    return (min1[x] <= 2 ? cnt1[x] : 0) + (min2[x] <= 2 ? cnt2[x] : 0);
  int mid = (L + R) >> 1;
  if (tag[x]) down(x);
  return query(L, mid, x << 1, l, r) + query(mid + 1, R, (x << 1) | 1, l, r);
}
int main() {
  N = read();
  for (int i = 1; i <= N; i++) a[i] = read(), pos[a[i]] = i;
  bool p1, p2;
  int c1, c2;
  buildTree(1, N, 1);
  for (int i = 1; i <= N; i++) {
    vis[pos[i]] = 1;
    p1 = vis[pos[i] - 1];
    p2 = vis[pos[i] + 1];
    if (p1 && p2) {
      c1 = a[pos[i] - 1];
      c2 = a[pos[i] + 1];
      if (c1 > c2) swap(c1, c2);
      update(1, N, 1, c2 + 1, i, 1);
      update(1, N, 1, 1, c1, -1);
    } else if (p1 || p2) {
      if (p1)
        c1 = a[pos[i] - 1];
      else
        c1 = a[pos[i] + 1];
      update(1, N, 1, c1 + 1, i, 1);
    } else
      update(1, N, 1, 1, i, 1);
    Ans += query(1, N, 1, 1, i);
  }
  printf("%lld", Ans - N);
  return 0;
}
