#include <bits/stdc++.h>
using namespace std;
inline int read() {
  static int r;
  static char c;
  r = 0, c = getchar();
  while (c < '0' || c > '9') c = getchar();
  while (c >= '0' && c <= '9') r = r * 10 + (c - '0'), c = getchar();
  return r;
}
template <typename T>
inline void print(T* a, int n) {
  for (int i = 1; i < n; ++i) cout << a[i] << " ";
  cout << a[n] << endl;
}
const int INFI = 123456789;
int n, a[300000 + 1], p[300000 + 1];
long long ans = 0LL;
struct node {
  int m, mc, m2, m2c, d;
} tree[300000 * 5];
inline node update(node l, node r) {
  static node ret;
  ret = l;
  ret.d = 0;
  if (r.m < ret.m) {
    ret.m2 = ret.m, ret.m2c = ret.mc;
    ret.m = r.m, ret.mc = r.mc;
  } else if (r.m == ret.m) {
    ret.mc += r.mc;
  } else if (r.m < ret.m2) {
    ret.m2 = r.m, ret.m2c = r.mc;
  } else if (r.m == ret.m2) {
    ret.m2c += r.mc;
  }
  if (r.m2 < ret.m2) {
    ret.m2 = r.m2, ret.m2c = r.m2c;
  } else if (r.m2 == ret.m2) {
    ret.m2c += r.m2c;
  }
  return ret;
}
inline void applyDelta(int x, int d) {
  tree[x].d += d, tree[x].m += d, tree[x].m2 += d;
}
inline void push(int x) {
  if (tree[x].d != 0) {
    applyDelta(((x) << 1), tree[x].d);
    applyDelta(((x) << 1 | 1), tree[x].d);
    tree[x].d = 0;
  }
}
void modify(int x, int l, int r, int s, int t, int v) {
  if (l == s && r == t) {
    applyDelta(x, v);
    return;
  }
  push(x);
  int mid = l + r >> 1;
  if (t <= mid)
    modify(((x) << 1), l, mid, s, t, v);
  else if (s > mid)
    modify(((x) << 1 | 1), mid + 1, r, s, t, v);
  else {
    modify(((x) << 1), l, mid, s, mid, v);
    modify(((x) << 1 | 1), mid + 1, r, mid + 1, t, v);
  }
  tree[x] = update(tree[((x) << 1)], tree[((x) << 1 | 1)]);
}
node query(int x, int l, int r, int s, int t) {
  if (l == s && r == t) return tree[x];
  push(x);
  int mid = l + r >> 1;
  if (t <= mid)
    return query(((x) << 1), l, mid, s, t);
  else if (s > mid)
    return query(((x) << 1 | 1), mid + 1, r, s, t);
  return update(query(((x) << 1), l, mid, s, mid),
                query(((x) << 1 | 1), mid + 1, r, mid + 1, t));
}
inline int query(int i) {
  static node cur;
  cur = query(1, 1, n, i, n);
  if (cur.m2 <= 2) return cur.mc + cur.m2c;
  if (cur.m <= 2) return cur.mc;
  return 0;
}
void build(int x, int l, int r) {
  if (l == r) {
    tree[x].m = 0, tree[x].m2 = INFI;
    tree[x].mc = 1, tree[x].m2c = 0;
    tree[x].d = 0;
    return;
  }
  int mid = l + r >> 1;
  build(((x) << 1), l, mid);
  build(((x) << 1 | 1), mid + 1, r);
  tree[x] = update(tree[((x) << 1)], tree[((x) << 1 | 1)]);
}
int main(int argc, char* argv[]) {
  n = read();
  for (int i = 1; i <= n; ++i) a[i] = read();
  for (int i = 1; i <= n; ++i) p[a[i]] = i;
  build(1, 1, n);
  for (int i = n; i > 0; --i) {
    int l = 0, r = 0;
    if (p[i] > 1 && a[p[i] - 1] > i) l = a[p[i] - 1];
    if (p[i] < n && a[p[i] + 1] > i) r = a[p[i] + 1];
    if (l > r) swap(l, r);
    if (l != 0) {
      modify(1, 1, n, r, n, -1);
      modify(1, 1, n, i, l - 1, 1);
    } else if (r != 0) {
      modify(1, 1, n, i, r - 1, 1);
    } else {
      modify(1, 1, n, i, n, 1);
    }
    ans += query(i);
  }
  cout << ans - n << endl;
  fclose(stdin);
  fclose(stdout);
  return 0;
}
