#include <bits/stdc++.h>
using namespace std;
struct Tnode {
  int tmin, tot1, tot2, cover;
} tree[300005 * 4];
int n, a[300005], p[300005];
long long ans = 0;
void init() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
}
void ins(int step, int l, int r, int ll, int rr, int x) {
  if (ll <= l && rr >= r) {
    tree[step].cover += x;
    return;
  }
  int mid = (l + r) >> 1;
  if (tree[step].cover) {
    tree[step << 1].cover += tree[step].cover;
    tree[step << 1 | 1].cover += tree[step].cover;
    tree[step].cover = 0;
  }
  if (ll <= mid) ins(step << 1, l, mid, ll, rr, x);
  if (rr > mid) ins(step << 1 | 1, mid + 1, r, ll, rr, x);
  tree[step].tmin = tree[step << 1].tmin + tree[step << 1].cover <
                            tree[step << 1 | 1].tmin + tree[step << 1 | 1].cover
                        ? tree[step << 1].tmin + tree[step << 1].cover
                        : tree[step << 1 | 1].tmin + tree[step << 1 | 1].cover;
  tree[step].tot1 = tree[step].tot2 = 0;
  if (tree[step << 1].tmin + tree[step << 1].cover == tree[step].tmin) {
    tree[step].tot1 += tree[step << 1].tot1;
    tree[step].tot2 += tree[step << 1].tot2;
  } else if (tree[step << 1].tmin + tree[step << 1].cover ==
             tree[step].tmin + 1)
    tree[step].tot2 += tree[step << 1].tot1;
  if (tree[step << 1 | 1].tmin + tree[step << 1 | 1].cover == tree[step].tmin) {
    tree[step].tot1 += tree[step << 1 | 1].tot1;
    tree[step].tot2 += tree[step << 1 | 1].tot2;
  } else if (tree[step << 1 | 1].tmin + tree[step << 1 | 1].cover ==
             tree[step].tmin + 1)
    tree[step].tot2 += tree[step << 1 | 1].tot1;
}
void prepare(int step, int l, int r) {
  tree[step].tot1 = r - l + 1;
  if (l == r) return;
  int mid = (l + r) >> 1;
  prepare(step << 1, l, mid);
  prepare(step << 1 | 1, mid + 1, r);
}
int query(int step, int l, int r, int ll, int rr) {
  if (ll <= l && rr >= r) {
    if (tree[step].tmin + tree[step].cover == 1)
      return tree[step].tot1 + tree[step].tot2;
    else if (tree[step].tmin + tree[step].cover == 2)
      return tree[step].tot1;
    else
      return 0;
  }
  int mid = (l + r) >> 1, t = 0;
  if (tree[step].cover) {
    tree[step << 1].cover += tree[step].cover;
    tree[step << 1 | 1].cover += tree[step].cover;
    tree[step].cover = 0;
  }
  if (ll <= mid) t += query(step << 1, l, mid, ll, rr);
  if (rr > mid) t += query(step << 1 | 1, mid + 1, r, ll, rr);
  tree[step].tmin = tree[step << 1].tmin + tree[step << 1].cover <
                            tree[step << 1 | 1].tmin + tree[step << 1 | 1].cover
                        ? tree[step << 1].tmin + tree[step << 1].cover
                        : tree[step << 1 | 1].tmin + tree[step << 1 | 1].cover;
  tree[step].tot1 = tree[step].tot2 = 0;
  if (tree[step << 1].tmin + tree[step << 1].cover == tree[step].tmin) {
    tree[step].tot1 += tree[step << 1].tot1;
    tree[step].tot2 += tree[step << 1].tot2;
  } else if (tree[step << 1].tmin + tree[step << 1].cover ==
             tree[step].tmin + 1)
    tree[step].tot2 += tree[step << 1].tot1;
  if (tree[step << 1 | 1].tmin + tree[step << 1 | 1].cover == tree[step].tmin) {
    tree[step].tot1 += tree[step << 1 | 1].tot1;
    tree[step].tot2 += tree[step << 1 | 1].tot2;
  } else if (tree[step << 1 | 1].tmin + tree[step << 1 | 1].cover ==
             tree[step].tmin + 1)
    tree[step].tot2 += tree[step << 1 | 1].tot1;
  return t;
}
void work() {
  int i, j, k, x, y;
  for (i = 1; i <= n; i++) p[a[i]] = i;
  prepare(1, 1, n);
  for (i = 1; i <= n; i++) {
    x = a[p[i] - 1];
    if (x > i) x = 0;
    y = a[p[i] + 1];
    if (y > i) y = 0;
    if (x < y) swap(x, y);
    if (!x && !y)
      ins(1, 1, n, 1, i, 1);
    else if (!y) {
      ins(1, 1, n, x + 1, i, 1);
    } else {
      ins(1, 1, n, 1, y, -1);
      ins(1, 1, n, x + 1, i, 1);
    }
    if (i != 1) ans += query(1, 1, n, 1, i - 1);
  }
  cout << ans << endl;
}
int main() {
  init();
  work();
  return 0;
}
