#include <bits/stdc++.h>
using namespace std;
vector<int> v;
int laz[300002 * 4];
int mp[300002 * 4];
struct st {
  pair<int, int> cn[2];
  st() {
    cn[0].first = INT_MAX / 2 - 1;
    cn[0].second = cn[1].second = 0;
    cn[1].first = INT_MAX / 2;
  }
};
st seg[300002 * 4];
st merge(st a, st b) {
  int i = 0;
  int j = 0;
  int idx = 0;
  st r;
  while (idx < 2) {
    if (a.cn[i].first == b.cn[j].first) {
      r.cn[idx] = make_pair(a.cn[i].first, a.cn[i].second + b.cn[j].second);
      idx++;
      i++;
      j++;
      continue;
    }
    if (a.cn[i].first < b.cn[j].first) {
      r.cn[idx] = a.cn[i];
      idx++;
      i++;
    } else {
      r.cn[idx] = b.cn[j];
      idx++;
      j++;
    }
  }
  return r;
}
inline void upd(int b) {
  seg[b].cn[0].first += laz[b];
  seg[b].cn[1].first += laz[b];
  if (b * 2 + 2 < 300002 * 4) {
    laz[b * 2 + 1] += laz[b];
    laz[b * 2 + 2] += laz[b];
  }
  laz[b] = 0;
}
inline void add(int b, int l, int r, int ll, int rr, int x) {
  if (ll >= rr) return;
  upd(b);
  if (r <= ll || rr <= l) return;
  if (ll <= l && r <= rr) {
    laz[b] += x;
    upd(b);
    return;
  }
  add(b * 2 + 1, l, (l + r) >> 1, ll, rr, x);
  add(b * 2 + 2, (l + r) >> 1, r, ll, rr, x);
  seg[b] = merge(seg[b * 2 + 1], seg[b * 2 + 2]);
}
inline st query(int b, int l, int r, int ll, int rr) {
  upd(b);
  if (r <= ll || rr <= l) return st();
  if (ll <= l && r <= rr) {
    return seg[b];
  }
  return merge(query(b * 2 + 1, l, (l + r) >> 1, ll, rr),
               query(b * 2 + 2, (l + r) >> 1, r, ll, rr));
}
inline void init(int b, int l, int r) {
  seg[b].cn[0].first = 1;
  seg[b].cn[0].second = r - l;
  if (l + 1 == r) {
    return;
  }
  init(b * 2 + 1, l, (l + r) >> 1);
  init(b * 2 + 2, (l + r) >> 1, r);
}
int main() {
  int n;
  cin >> n;
  v.assign(n, 0);
  for (int i = 0; i < n; i++) {
    int a;
    scanf("%d", &a);
    a--;
    v[a] = i;
    mp[v[a]] = a;
  }
  init(0, 0, n);
  long long int ans = 0;
  for (int i = 0; i < n; i++) {
    int lef = -1;
    int rig = -1;
    if (v[i]) {
      if (mp[v[i] - 1] < i) {
        lef = mp[v[i] - 1];
      }
    }
    if (v[i] + 1 < n) {
      if (mp[v[i] + 1] < i) {
        rig = mp[v[i] + 1];
      }
    }
    if (lef > rig) swap(lef, rig);
    if (lef == -1 && rig == -1) {
      add(0, 0, n, 0, i, 1);
    } else {
      add(0, 0, n, rig + 1, i, 1);
      if (lef != -1) {
        add(0, 0, n, 0, lef + 1, -1);
      }
    }
    auto f = query(0, 0, n, 0, i + 1);
    if (f.cn[0].first <= 2) {
      ans += f.cn[0].second;
    }
    if (f.cn[1].first <= 2) {
      ans += f.cn[1].second;
    }
  }
  printf("%lld\n", ans - n);
  return 0;
}
