#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 5;
int n;
int b[maxn], pos[maxn], c[maxn];
long long ans;
struct node {
  int mx, mn, cx, cn, tag;
} a[maxn << 2];
void maintain(int k) {
  int l = k << 1, r = l ^ 1;
  a[k].mx = min(a[l].mx, a[r].mx);
  if (a[l].mx < a[r].mx) {
    a[k].cx = a[l].cx;
    a[k].mn = min(a[l].mn, a[r].mx);
    if (a[l].mn < a[r].mx)
      a[k].cn = a[l].cn;
    else if (a[l].mn > a[r].mx)
      a[k].cn = a[r].cx;
    else
      a[k].cn = a[l].cn + a[r].cx;
  } else if (a[l].mx > a[r].mx) {
    a[k].cx = a[r].cx;
    a[k].mn = min(a[l].mx, a[r].mn);
    if (a[l].mx < a[r].mn)
      a[k].cn = a[l].cx;
    else if (a[l].mx > a[r].mn)
      a[k].cn = a[r].cn;
    else
      a[k].cn = a[l].cx + a[r].cn;
  } else {
    a[k].cx = a[l].cx + a[r].cx;
    a[k].mn = min(a[l].mn, a[r].mn);
    if (a[l].mn < a[r].mn)
      a[k].cn = a[l].cn;
    else if (a[l].mn > a[r].mn)
      a[k].cn = a[r].cn;
    else
      a[k].cn = a[l].cn + a[r].cn;
  }
}
void tag(int k, int x) {
  a[k].mx += x;
  a[k].mn += x;
  a[k].tag += x;
}
void pushdown(int k, bool o) {
  if (a[k].tag) {
    if (!o) {
      tag(k << 1, a[k].tag);
      tag(k << 1 ^ 1, a[k].tag);
    }
    a[k].tag = 0;
  }
}
void build(int k, int l, int r) {
  if (l == r) {
    a[k].mx = c[l], a[k].mn = INT_MAX / 2, a[k].cx = 1;
    return;
  }
  int mid = (l + r) >> 1;
  build(k << 1, l, mid);
  build(k << 1 ^ 1, mid + 1, r);
  maintain(k);
}
void add(int k, int l, int r, int s, int t, int x) {
  int mid = (l + r) >> 1;
  pushdown(k, l == r);
  if (l == s && r == t) {
    tag(k, x);
    return;
  }
  if (t <= mid)
    add(k << 1, l, mid, s, t, x);
  else if (s > mid)
    add(k << 1 ^ 1, mid + 1, r, s, t, x);
  else
    add(k << 1, l, mid, s, mid, x), add(k << 1 ^ 1, mid + 1, r, mid + 1, t, x);
  maintain(k);
}
int query(int k, int l, int r, int s, int t) {
  int mid = (l + r) >> 1, res = 0;
  pushdown(k, l == r);
  if (l == s && r == t) {
    if (a[k].mx == 1 || a[k].mx == 2) res += a[k].cx;
    if (a[k].mn == 1 || a[k].mn == 2) res += a[k].cn;
    return res;
  }
  if (t <= mid) return query(k << 1, l, mid, s, t);
  if (s > mid) return query(k << 1 ^ 1, mid + 1, r, s, t);
  return query(k << 1, l, mid, s, mid) +
         query(k << 1 ^ 1, mid + 1, r, mid + 1, t);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &b[i]), pos[b[i]] = i;
  c[n] = 1;
  build(1, 1, n);
  for (int i = n - 1; i >= 1; i--) {
    int l = b[pos[i] - 1], r = b[pos[i] + 1];
    if (l > r) swap(l, r);
    if (l) {
      if (l > i && r > i)
        add(1, 1, n, i, l - 1, 1), add(1, 1, n, r, n, -1);
      else if (l < i && r < i)
        add(1, 1, n, i, n, 1);
      else
        add(1, 1, n, i, r - 1, 1);
    } else if (r < i)
      add(1, 1, n, i, n, 1);
    else
      add(1, 1, n, i, r - 1, 1);
    ans += query(1, 1, n, i + 1, n);
  }
  printf("%I64d", ans);
  return 0;
}
