#include <bits/stdc++.h>
using namespace std;
const int maxn = 400008;
int n, p[maxn], a[maxn];
long long ans;
struct arr {
  int x, y;
  arr() {}
  arr(int x1, int y1) {
    x = x1;
    y = y1;
  }
  bool operator<(const arr &t) const { return x < t.x; }
  friend arr operator+(const arr &a, const arr &b) {
    if (a < b) return a;
    if (b < a) return b;
    return arr(a.x, a.y + b.y);
  }
};
struct Seg {
  arr m1[maxn << 2], m2[maxn << 2];
  int size, d[maxn << 2], h;
  void make(int x, int v) {
    d[x] += v;
    m1[x].x += v;
    m2[x].x += v;
  }
  void down(int x) {
    if (d[x]) make(x << 1, d[x]), make(x << 1 ^ 1, d[x]), d[x] = 0;
  }
  void update(int x, int y, int z) {
    m2[x] = m2[y] + m2[z];
    if (m1[y] < m1[z])
      m2[x] = m2[x] + m1[z];
    else if (m1[z] < m1[y])
      m2[x] = m2[x] + m1[y];
    m1[x] = m1[y] + m1[z];
  }
  void build() {
    size = 1;
    while (size < n + 2) size <<= 1, h++;
    for (int i = 1; i <= n; i++) m1[i + size].y = 1, m2[i + size].x = 1e9;
    for (int i = size - 1; i >= 1; i--) update(i, i << 1, i << 1 ^ 1);
  }
  void modify(int l, int r, int x) {
    if (l > r || l <= 0 || r > n) return;
    l += size - 1, r += size + 1;
    int l1 = l, r1 = r;
    for (int i = h; i >= 1; i--) down(l >> i), down(r >> i);
    while (l ^ r ^ 1) {
      if (l & 1 ^ 1) make(l ^ 1, x);
      if (r & 1) make(r ^ 1, x);
      l >>= 1;
      r >>= 1;
    }
    for (l1 >>= 1, r1 >>= 1; l1; l1 >>= 1, r1 >>= 1) {
      update(l1, l1 << 1, l1 << 1 ^ 1);
      if (l1 != r1) update(r1, r1 << 1, r1 << 1 ^ 1);
    }
  }
  int ask(int l, int r) {
    l += size - 1;
    r += size + 1;
    int t = 0;
    for (int i = h; i >= 1; i--) down(l >> i), down(r >> i);
    m1[t].x = m2[t].x = 1e9;
    m1[t].y = m2[t].y = 0;
    while (l ^ r ^ 1) {
      if (l & 1 ^ 1) update(t, t, l ^ 1);
      if (r & 1) update(t, t, r ^ 1);
      l >>= 1;
      r >>= 1;
    }
    return (m1[t].x <= 2 ? m1[t].y : 0) + (m2[t].x <= 2 ? m2[t].y : 0);
  }
} Segtree;
struct Tprogram {
  void open() {
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
  }
  void close() {}
  void init() {
    scanf("%d", &n);
    int x;
    for (int i = 1; i <= n; i++) scanf("%d", &x), p[x] = i, a[i] = x;
  }
  void work() {
    Segtree.build();
    for (int i = 1; i <= n; i++) {
      int t1 = a[p[i] - 1], t2 = a[p[i] + 1];
      if (t1 > i) t1 = 0;
      if (t2 > i) t2 = 0;
      if (t1 > t2) swap(t1, t2);
      Segtree.modify(t2 + 1, i, 1);
      Segtree.modify(1, t1, -1);
      ans += Segtree.ask(1, i) - 1;
    }
    printf("%I64d\n", ans);
  }
} Program;
int main() {
  Program.init();
  Program.work();
  return 0;
}
