#include <bits/stdc++.h>
using namespace std;
struct node {
  int l, r, lc, rc, d1, d2, c1, c2, lz;
} lt[2 * 310000];
int n, a[310000], w[310000], d[310000], s[310000], tl;
bool b[310000];
long long ans;
void down(int now) {
  int lc = lt[now].lc, rc = lt[now].rc;
  if (lc) lt[lc].lz += lt[now].lz;
  if (rc) lt[rc].lz += lt[now].lz;
  lt[now].d1 += lt[now].lz;
  lt[now].d2 += lt[now].lz;
  lt[now].lz = 0;
}
void upd(int now) {
  int lc = lt[now].lc, rc = lt[now].rc, d1, c1, d2, c2;
  if (lt[lc].lz) down(lc);
  if (lt[rc].lz) down(rc);
  d1 = d2 = 999999;
  if (d1 > lt[lc].d1)
    d2 = d1, c2 = c1, d1 = lt[lc].d1, c1 = lt[lc].c1;
  else if (lt[lc].d1 == d1)
    c1 += lt[lc].c1;
  else if (d2 > lt[lc].d1)
    d2 = lt[lc].d1, c2 = lt[lc].c1;
  else if (d2 == lt[lc].d1)
    c2 += lt[lc].c1;
  if (d1 > lt[lc].d2)
    d2 = d1, c2 = c1, d1 = lt[lc].d2, c1 = lt[lc].c2;
  else if (lt[lc].d2 == d1)
    c1 += lt[lc].c2;
  else if (d2 > lt[lc].d2)
    d2 = lt[lc].d2, c2 = lt[lc].c2;
  else if (d2 == lt[lc].d2)
    c2 += lt[lc].c2;
  if (d1 > lt[rc].d1)
    d2 = d1, c2 = c1, d1 = lt[rc].d1, c1 = lt[rc].c1;
  else if (lt[rc].d1 == d1)
    c1 += lt[rc].c1;
  else if (d2 > lt[rc].d1)
    d2 = lt[rc].d1, c2 = lt[rc].c1;
  else if (d2 == lt[rc].d1)
    c2 += lt[rc].c1;
  if (d1 > lt[rc].d2)
    d2 = d1, c2 = c1, d1 = lt[rc].d2, c1 = lt[rc].c2;
  else if (lt[rc].d2 == d1)
    c1 += lt[rc].c2;
  else if (d2 > lt[rc].d2)
    d2 = lt[rc].d2, c2 = lt[rc].c2;
  else if (d2 == lt[rc].d2)
    c2 += lt[rc].c2;
  lt[now].d1 = d1;
  lt[now].c1 = c1;
  lt[now].d2 = d2;
  lt[now].c2 = c2;
}
void bt(int l, int r) {
  int now = ++tl;
  lt[now].l = l;
  lt[now].r = r;
  if (l < r) {
    int mid = (l + r) / 2;
    lt[now].lc = tl + 1;
    bt(l, mid);
    lt[now].rc = tl + 1;
    bt(mid + 1, r);
    upd(now);
  } else
    lt[now].d1 = s[l], lt[now].c1 = 1, lt[now].d2 = 999999;
}
void change(int now, int l, int r, int d) {
  if (l > r) return;
  int lc = lt[now].lc, rc = lt[now].rc, mid = (lt[now].l + lt[now].r) / 2;
  if (lt[now].l == l && lt[now].r == r) {
    lt[now].lz += d;
    return;
  }
  if (mid >= r)
    change(lc, l, r, d);
  else if (l > mid)
    change(rc, l, r, d);
  else
    change(lc, l, mid, d), change(rc, mid + 1, r, d);
  upd(now);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    w[a[i]] = i;
  }
  for (int i = 1; i <= n; i++) b[i] = 0;
  for (int i = 1; i <= n; i++) {
    d[i] = 1;
    if (b[w[i] - 1]) d[i]--;
    if (b[w[i] + 1]) d[i]--;
    b[w[i]] = 1;
  }
  for (int i = 1; i <= n; i++) s[i] = s[i - 1] + d[i];
  bt(1, n);
  for (int i = 1; i <= n; i++) {
    ans += lt[1].c1;
    if (lt[1].d2 == 2) ans += lt[1].c2;
    change(1, i, i, 999999);
    change(1, i + 1, n, -d[i]);
    if (b[w[i] - 1]) change(1, a[w[i] - 1], n, 1), d[a[w[i] - 1]]++;
    if (b[w[i] + 1]) change(1, a[w[i] + 1], n, 1), d[a[w[i] + 1]]++;
    b[w[i]] = 0;
  }
  ans -= n;
  cout << ans << endl;
  return 0;
}
