#include <bits/stdc++.h>
using namespace std;
using LL = int64_t;
using pii = pair<int, int>;
const double EPS = 1e-9;
const double PI = 2 * asin(1);
const int INF = 0x3fffffff;
const LL LINF = 0x3fffffffffffffff;
const int MX = 300000 + 10;
struct Segment_tree {
  vector<LL> val, tol, sum, lazy;
  void initial(int n) {
    val.clear(), val.resize(n << 2);
    tol.clear(), tol.resize(n << 2);
    sum.clear(), sum.resize(n << 2);
    lazy.clear(), lazy.resize(n << 2);
  }
  int ls(int root) { return root << 1; }
  int rs(int root) { return root << 1 | 1; }
  int mid(int l, int r) { return (l + r) >> 1; }
  void push_up(int root) {
    int l = ls(root), r = rs(root);
    val[root] = min(val[l], val[r]);
    auto v = val[root];
    tol[root] = 0;
    if (v == val[l]) tol[root] += tol[l];
    if (v == val[r]) tol[root] += tol[r];
    sum[root] = 0;
    if (v == val[l] - 1) sum[root] += tol[l];
    if (v == val[r] - 1) sum[root] += tol[r];
    if (v == val[l]) sum[root] += sum[l];
    if (v == val[r]) sum[root] += sum[r];
  }
  void push_down(int root) {
    if (lazy[root] == 0) return;
    int l = ls(root), r = rs(root);
    auto k = lazy[root];
    lazy[root] = 0;
    val[l] += k, val[r] += k;
    lazy[l] += k, lazy[r] += k;
  }
  void built(int root, int l, int r) {
    tol[root] = r - l + 1;
    if (l == r) return;
    built(ls(root), l, mid(l, r));
    built(rs(root), mid(l, r) + 1, r);
  }
  void update_pt(int root, int l, int r, int u, int v, int k) {
    if (u <= l && v >= r) {
      val[root] += k;
      lazy[root] += k;
      return;
    }
    push_down(root);
    if (u <= mid(l, r)) update_pt(ls(root), l, mid(l, r), u, v, k);
    if (v > mid(l, r)) update_pt(rs(root), mid(l, r) + 1, r, u, v, k);
    push_up(root);
  }
  LL query(int root, int l, int r, int u, int v) {
    if (u <= l && v >= r) {
      LL ans = 0;
      if (val[root] <= 2) ans += tol[root];
      if (val[root] == 1) ans += sum[root];
      return ans;
    }
    push_down(root);
    if (v <= mid(l, r)) return query(ls(root), l, mid(l, r), u, v);
    if (u > mid(l, r)) return query(rs(root), mid(l, r) + 1, r, u, v);
    return query(ls(root), l, mid(l, r), u, v) +
           query(rs(root), mid(l, r) + 1, r, u, v);
  }
};
int g_n;
int p[MX], a[MX];
Segment_tree sg_tr;
void pretreat() {}
bool input() {
  cin >> g_n;
  if (cin.eof()) return false;
  memset(p, 0, sizeof(p));
  memset(a, 0, sizeof(a));
  for (int i = 1, t; i <= g_n; ++i) {
    scanf(" %d", &t);
    p[t] = i;
  }
  return true;
}
void solve() {
  sg_tr.initial(g_n);
  sg_tr.built(1, 1, g_n);
  LL ans = 0;
  for (int i = g_n; i != 0; --i) {
    a[p[i]] = i;
    int u = a[p[i] - 1], v = a[p[i] + 1];
    if (u > v) swap(u, v);
    if (u != 0) {
      sg_tr.update_pt(1, 1, g_n, i, u - 1, 1);
      sg_tr.update_pt(1, 1, g_n, v, g_n, -1);
    } else if (v != 0) {
      sg_tr.update_pt(1, 1, g_n, i, v - 1, 1);
    } else
      sg_tr.update_pt(1, 1, g_n, i, g_n, 1);
    ans += sg_tr.query(1, 1, g_n, i, g_n);
  }
  cout << ans - g_n << endl;
}
int main() {
  pretreat();
  while (input()) {
    solve();
  }
  return 0;
}
