#include <bits/stdc++.h>
using namespace std;
int a[300010], p[300010], mn1[4000010], c1[4000010], mn2[4000010], c2[4000010],
    tag[4000010], n;
void down(int p) {
  if (tag[p]) {
    mn1[p] += tag[p];
    mn2[p] += tag[p];
    tag[p * 2] += tag[p];
    tag[p * 2 + 1] += tag[p];
    tag[p] = 0;
  }
}
int calc(int x1, int x2, int y1, int y2, int &v, int &c) {
  if (x1 == x2) {
    v = x1;
    c = y1 + y2;
    return 0;
  }
  if (x1 < x2) {
    v = x1;
    c = y1;
    return 1;
  }
  v = x2;
  c = y2;
  return -1;
}
void up(int p) {
  down(p);
  down(p * 2);
  down(p * 2 + 1);
  switch (calc(mn1[p * 2], mn1[p * 2 + 1], c1[p * 2], c1[p * 2 + 1], mn1[p],
               c1[p])) {
    case 0:
      calc(mn2[p * 2], mn2[p * 2 + 1], c2[p * 2], c2[p * 2 + 1], mn2[p], c2[p]);
      break;
    case 1:
      calc(mn2[p * 2], mn1[p * 2 + 1], c2[p * 2], c1[p * 2 + 1], mn2[p], c2[p]);
      break;
    case -1:
      calc(mn1[p * 2], mn2[p * 2 + 1], c1[p * 2], c2[p * 2 + 1], mn2[p], c2[p]);
      break;
  }
}
void add(int p, int L, int R, int l, int r, int x) {
  down(p);
  if (L == l && r == R) {
    tag[p] += x;
    return;
  }
  int mid = (L + R) / 2;
  if (r <= mid)
    add(p * 2, L, mid, l, r, x);
  else {
    if (l > mid)
      add(p * 2 + 1, mid + 1, R, l, r, x);
    else {
      add(p * 2, L, mid, l, mid, x);
      add(p * 2 + 1, mid + 1, R, mid + 1, r, x);
    }
  }
  up(p);
}
int qry(int p, int L, int R, int l, int r) {
  down(p);
  int ret = 0;
  if (L == l && r == R) {
    if (mn1[p] <= 2) ret += c1[p];
    if (mn2[p] <= 2) ret += c2[p];
    return ret;
  }
  int mid = (L + R) / 2;
  if (r <= mid) return qry(p * 2, L, mid, l, r);
  if (l > mid) return qry(p * 2 + 1, mid + 1, R, l, r);
  return qry(p * 2, L, mid, l, mid) + qry(p * 2 + 1, mid + 1, R, mid + 1, r);
}
void in(int p, int L, int R, int x) {
  if (L == R) {
    mn1[p] = 0;
    c1[p] = 1;
    return;
  }
  down(p);
  int mid = (L + R) / 2;
  if (x <= mid)
    in(p * 2, L, mid, x);
  else
    in(p * 2 + 1, mid + 1, R, x);
  up(p);
}
int main() {
  int i, j, k, q, x, y, z;
  long long ans = 0;
  scanf("%d", &n);
  for (i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (i = 1; i <= n; i++) p[a[i]] = i;
  memset(mn1, 0x3f, sizeof(mn1));
  memset(mn2, 0x3f, sizeof(mn2));
  for (i = 1; i <= n; i++) {
    in(1, 1, n, i);
    x = p[i] == 1 ? n + 1 : a[p[i] - 1];
    y = p[i] == n ? n + 1 : a[p[i] + 1];
    if (x < y) swap(x, y);
    if (y > i)
      add(1, 1, n, 1, i, 1);
    else {
      if (x > i)
        add(1, 1, n, y + 1, i, 1);
      else {
        add(1, 1, n, x + 1, i, 1);
        add(1, 1, n, 1, y, -1);
      }
    }
    ans += qry(1, 1, n, 1, i);
  }
  printf("%I64d\n", ans - n);
}
