#include <bits/stdc++.h>
using namespace std;
int N, P;
int A[300000];
int aa[300000];
const int n = 1 << 19;
struct SegTree {
  pair<int, int> m1[n * 2 - 1], m2[n * 2 - 1];
  int dat[n * 2 - 1];
  void init_v(int k) {
    m1[k] = make_pair(m1[k * 2 + 1].first, 0);
    m2[k] = make_pair(m2[k * 2 + 1].first, 0);
    if (m1[k].first > m1[k * 2 + 2].first)
      m2[k].first = m1[k].first, m1[k].first = m1[k * 2 + 2].first;
    else if (m2[k].first > m1[k * 2 + 2].first &&
             m1[k].first != m1[k * 2 + 2].first)
      m2[k].first = m1[k * 2 + 2].first;
    if (m2[k].first > m2[k * 2 + 2].first && m1[k].first != m2[k * 2 + 2].first)
      m2[k].first = m2[k * 2 + 2].first;
    m1[k].second = m2[k].second = 0;
    for (int(v) = (k * 2 + 1); (v) < (k * 2 + 3); (v)++) {
      if (m1[v].first == m1[k].first) m1[k].second += m1[v].second;
      if (m1[v].first == m2[k].first) m2[k].second += m1[v].second;
      if (m2[v].first == m2[k].first) m2[k].second += m2[v].second;
    }
    m1[k].first += dat[k];
    m2[k].first += dat[k];
  }
  SegTree() {
    for (int(i) = 0; (i) < (n); (i)++) {
      m1[i + n - 1] = make_pair(0, 1);
      m2[i + n - 1] = make_pair((1 << 29), 0);
    }
    for (int i = n - 2; i >= 0; i--) init_v(i);
  }
  void add(int a, int b, int k, int l, int r, int s) {
    if (r <= a || b <= l) return;
    if (a <= l && r <= b) {
      dat[k] += s;
      m1[k].first += s;
      m2[k].first += s;
    } else {
      add(a, b, k * 2 + 1, l, (l + r) / 2, s);
      add(a, b, k * 2 + 2, (l + r) / 2, r, s);
      init_v(k);
    }
  }
  int get(int k) {
    k += n - 1;
    int s = dat[k];
    while (k) k = (k - 1) / 2, s += dat[k];
    return s;
  }
} seg;
int info[300000];
void update(int id) {
  if (aa[id] >= (1 << 29)) return;
  int cc = 0;
  if (id - 1 >= 0 && aa[id - 1] < aa[id]) cc++;
  if (id + 1 < N && aa[id + 1] < aa[id]) cc++;
  cc = 1 - cc;
  int i = aa[id];
  int dif = cc - info[i];
  if (dif) seg.add(i, n, 0, 0, n, dif);
  info[i] = cc;
}
int main() {
  scanf("%d", &N);
  for (int(i) = 0; (i) < (N); (i)++) scanf("%d", &aa[i]), A[--aa[i]] = i;
  for (int(i) = 0; (i) < (N); (i)++) {
    int cc = 0;
    int id = A[i];
    if (id - 1 >= 0 && aa[id - 1] < aa[id]) cc++;
    if (id + 1 < N && aa[id + 1] < aa[id]) cc++;
    cc = 1 - cc;
    if (cc) seg.add(i, n, 0, 0, n, cc);
    info[i] = cc;
  }
  seg.add(N, n, 0, 0, n, 1 << 28);
  long long res = 0;
  for (int(i) = 0; (i) < (N); (i)++) {
    seg.add(i, i + 1, 0, 0, n, (1 << 29));
    if (seg.m1[0].first <= 2) res += seg.m1[0].second;
    if (seg.m2[0].first <= 2) res += seg.m2[0].second;
    int id = A[i];
    aa[id] = (1 << 29);
    if (info[i]) seg.add(i, n, 0, 0, n, -info[i]);
    if (id - 1 >= 0) update(id - 1);
    if (id + 1 < N) update(id + 1);
  }
  cout << res << endl;
}
