#include <bits/stdc++.h>
using namespace std;
int read() {
  char ch = getchar();
  int x = 0, pd = 0;
  while (ch < '0' || ch > '9') pd |= ch == '-', ch = getchar();
  while ('0' <= ch && ch <= '9')
    x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
  return pd ? -x : x;
}
const int maxn = 300005;
int n, p[maxn], vis[maxn];
struct node {
  int val, cnt;
  bool operator<(const node x) const { return val < x.val; }
} min1[maxn << 2], min2[maxn << 2];
int t[maxn << 2];
void _sort(node &a, node &b, node &c, node &d) {
  if (b < a) swap(a, b);
  if (c < a) swap(a, c);
  if (d < a) swap(a, d);
  if (c < b) swap(b, c);
  if (d < b) swap(b, d);
  if (d < c) swap(c, d);
}
void pushup(int rt) {
  node x = (rt << 1)[min1], y = (rt << 1)[min2], z = (rt << 1 | 1)[min1],
       w = (rt << 1 | 1)[min2];
  _sort(x, y, z, w);
  rt[min1] = x;
  if (y.val == x.val) {
    rt[min1].cnt += y.cnt;
    rt[min2] = z;
    if (w.val == z.val) rt[min2].cnt += w.cnt;
  } else {
    rt[min2] = y;
    if (z.val == y.val) rt[min2].cnt += z.cnt;
  }
}
void pushdown(int rt) {
  int _t = rt[t];
  (rt << 1)[min1].val += _t, (rt << 1)[min2].val += _t;
  (rt << 1 | 1)[min1].val += _t, (rt << 1 | 1)[min2].val += _t;
  (rt << 1)[t] += _t, (rt << 1 | 1)[t] += _t, rt[t] = 0;
}
void build(int rt, int l, int r) {
  if (l == r) {
    rt[min1].cnt = 1, rt[min2].val = 0x3f3f3f3f;
    return;
  }
  int mid = (l + r) >> 1;
  build((rt << 1), l, mid), build((rt << 1 | 1), mid + 1, r);
}
void update(int rt, int l, int r, int L, int R, int x) {
  if (L <= l && r <= R) {
    rt[min1].val += x, rt[min2].val += x;
    rt[t] += x;
    return;
  }
  if (rt[t]) pushdown(rt);
  int mid = (l + r) >> 1;
  if (L <= mid) update((rt << 1), l, mid, L, R, x);
  if (R > mid) update((rt << 1 | 1), mid + 1, r, L, R, x);
  pushup(rt);
}
long long ans;
int query(int rt, int l, int r, int L, int R) {
  if (L <= l && r <= R) {
    if (rt[min2].val <= 2) return rt[min1].cnt + rt[min2].cnt;
    return rt[min1].val <= 2 ? rt[min1].cnt : 0;
  }
  if (rt[t]) pushdown(rt);
  int mid = (l + r) >> 1;
  if (R <= mid) return query((rt << 1), l, mid, L, R);
  if (L > mid) return query((rt << 1 | 1), mid + 1, r, L, R);
  return query((rt << 1), l, mid, L, R) +
         query((rt << 1 | 1), mid + 1, r, L, R);
}
int main() {
  n = read();
  for (int i = 1; i <= n; i++) p[vis[i] = read()] = i;
  build(1, 1, n);
  for (int i = 1; i <= n; i++) {
    int x, y;
    if (p[i] == 1) {
      if (vis[2] > i)
        update(1, 1, n, 1, i, 1);
      else
        update(1, 1, n, vis[2] + 1, i, 1);
    } else if (p[i] == n) {
      if (vis[n - 1] > i)
        update(1, 1, n, 1, i, 1);
      else
        update(1, 1, n, vis[n - 1] + 1, i, 1);
    } else if (vis[p[i] - 1] > i && vis[p[i] + 1] > i)
      update(1, 1, n, 1, i, 1);
    else if ((vis[p[i] - 1] > i && vis[p[i] + 1] < i) ||
             (vis[p[i] - 1] < i && vis[p[i] + 1] > i)) {
      if (p[i] == 1)
        x = vis[2];
      else if (p[i] == n)
        x = vis[n - 1];
      else
        x = min(vis[p[i] - 1], vis[p[i] + 1]);
      update(1, 1, n, x + 1, i, 1);
    } else {
      x = min(vis[p[i] - 1], vis[p[i] + 1]);
      y = vis[p[i] - 1] + vis[p[i] + 1] - x;
      update(1, 1, n, x + 1, i, 1), update(1, 1, n, 1, y, -1);
    }
    if (i > 1) ans += query(1, 1, n, 1, i - 1);
  }
  printf("%lld\n", ans);
  return 0;
}
