#include <bits/stdc++.h>
using namespace std;
int n, a[500010], b[500010], mx[1500010], cmx[1500010], smx[1500010],
    scmx[1500010], sg[1500010], g[1500010], scg[1500010], cg[1500010],
    lz[1500010], ans;
long long mlby;
void pushup(int x) {
  if (mx[x * 2] == mx[x * 2 + 1]) {
    smx[x] = smx[x * 2] + smx[x * 2 + 1];
    mx[x] = mx[x * 2];
    cmx[x] = max(cmx[x * 2], cmx[x * 2 + 1]);
    scmx[x] = 0;
    if (cmx[x] == cmx[x * 2]) scmx[x] += scmx[x * 2];
    if (cmx[x] == cmx[x * 2 + 1]) scmx[x] += scmx[x * 2 + 1];
  } else if (mx[x * 2] > mx[x * 2 + 1]) {
    mx[x] = mx[x * 2];
    smx[x] = smx[x * 2];
    cmx[x] = max(cmx[x * 2], mx[x * 2 + 1]);
    scmx[x] = 0;
    if (cmx[x] == cmx[x * 2]) scmx[x] += scmx[x * 2];
    if (cmx[x] == mx[x * 2 + 1]) scmx[x] += smx[x * 2 + 1];
  } else {
    mx[x] = mx[x * 2 + 1];
    smx[x] = smx[x * 2 + 1];
    cmx[x] = max(mx[x * 2], cmx[x * 2 + 1]);
    scmx[x] = 0;
    if (cmx[x] == mx[x * 2]) scmx[x] += smx[x * 2];
    if (cmx[x] == cmx[x * 2 + 1]) scmx[x] += scmx[x * 2 + 1];
  }
}
void pushdown(int x) {
  if (lz[x]) {
    mx[x * 2] += lz[x];
    mx[x * 2 + 1] += lz[x];
    cmx[x * 2] += lz[x];
    cmx[x * 2 + 1] += lz[x];
    lz[x * 2] += lz[x];
    lz[x * 2 + 1] += lz[x];
    lz[x] = 0;
  }
}
void build(int x, int l, int r) {
  if (l == r) {
    mx[x] = l;
    smx[x] = 1;
    return;
  }
  int mid = (l + r) / 2;
  build(x * 2, l, mid);
  build(x * 2 + 1, mid + 1, r);
  pushup(x);
}
void ins(int x, int l, int r, int t, int k, int w) {
  if (l == t && r == k) {
    mx[x] += w;
    cmx[x] += w;
    lz[x] += w;
    return;
  }
  pushdown(x);
  int mid = (l + r) / 2;
  if (mid >= k)
    ins(x * 2, l, mid, t, k, w);
  else if (t > mid)
    ins(x * 2 + 1, mid + 1, r, t, k, w);
  else
    ins(x * 2, l, mid, t, mid, w), ins(x * 2 + 1, mid + 1, r, mid + 1, k, w);
  pushup(x);
}
void query(int x, int l, int r, int t, int k) {
  if (l == t && r == k) {
    g[x] = mx[x];
    sg[x] = smx[x];
    cg[x] = cmx[x];
    scg[x] = scmx[x];
    return;
  }
  pushdown(x);
  int mid = (l + r) / 2;
  if (mid >= k) {
    query(x * 2, l, mid, t, k);
    g[x] = g[x * 2];
    sg[x] = sg[x * 2];
    cg[x] = cg[x * 2];
    scg[x] = scg[x * 2];
  } else if (t > mid) {
    query(x * 2 + 1, mid + 1, r, t, k);
    g[x] = g[x * 2 + 1];
    sg[x] = sg[x * 2 + 1];
    cg[x] = cg[x * 2 + 1];
    scg[x] = scg[x * 2 + 1];
  } else {
    query(x * 2, l, mid, t, mid);
    query(x * 2 + 1, mid + 1, r, mid + 1, k);
    if (g[x * 2] == g[x * 2 + 1]) {
      sg[x] = sg[x * 2] + sg[x * 2 + 1];
      g[x] = g[x * 2];
      cg[x] = max(cg[x * 2], cg[x * 2 + 1]);
      scg[x] = 0;
      if (cg[x] == cg[x * 2]) scg[x] += scg[x * 2];
      if (cg[x] == cg[x * 2 + 1]) scg[x] += scg[x * 2 + 1];
    } else if (g[x * 2] > g[x * 2 + 1]) {
      g[x] = g[x * 2];
      sg[x] = sg[x * 2];
      cg[x] = max(cg[x * 2], g[x * 2 + 1]);
      scg[x] = 0;
      if (cg[x] == cg[x * 2]) scg[x] += scg[x * 2];
      if (cg[x] == g[x * 2 + 1]) scg[x] += sg[x * 2 + 1];
    } else {
      g[x] = g[x * 2 + 1];
      sg[x] = sg[x * 2 + 1];
      cg[x] = max(g[x * 2], cg[x * 2 + 1]);
      scg[x] = 0;
      if (cg[x] == g[x * 2]) scg[x] += sg[x * 2];
      if (cg[x] == cg[x * 2 + 1]) scg[x] += scg[x * 2 + 1];
    }
  }
}
int main() {
  int i;
  scanf("%d", &n);
  for (i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    b[a[i]] = i;
  }
  build(1, 1, n);
  for (i = 1; i <= n; i++) {
    if (b[i] > 1 && a[b[i] - 1] < i) ins(1, 1, n, 1, a[b[i] - 1], 1);
    if (b[i] < n && a[b[i] + 1] < i) ins(1, 1, n, 1, a[b[i] + 1], 1);
    query(1, 1, n, 1, i);
    ans = 0;
    if (g[1] >= i - 1) ans += sg[1];
    if (cg[1] >= i - 1) ans += scg[1];
    mlby += (long long)ans;
  }
  printf("%lld", mlby - (long long)n);
}
