#include <bits/stdc++.h>
using namespace std;
int m, n, j, k, l, i, o, p, __t, A[400000], pos[400000];
long long ans;
char ch;
void read(int &a) {
  for (ch = getchar(); (ch < '0' || ch > '9') && (ch != '-'); ch = getchar())
    ;
  if (ch == '-')
    a = 0, __t = -1;
  else
    a = ch - '0', __t = 1;
  for (ch = getchar(); ch >= '0' && ch <= '9'; ch = getchar())
    a = a * 10 + ch - '0';
  a *= __t;
}
pair<int, int> G[5];
struct segment_tree {
  int M[4 * 400000][2];
  int T[4 * 400000][2];
  int add_tag[4 * 400000];
  void updata(int P) {
    G[0].first = M[(P * 2)][0] + add_tag[(P * 2)];
    G[1].first = M[(P * 2)][1] + add_tag[(P * 2)];
    G[2].first = M[(P * 2 + 1)][0] + add_tag[(P * 2 + 1)];
    G[3].first = M[(P * 2 + 1)][1] + add_tag[(P * 2 + 1)];
    G[0].second = T[(P * 2)][0];
    G[1].second = T[(P * 2)][1];
    G[2].second = T[(P * 2 + 1)][0];
    G[3].second = T[(P * 2 + 1)][1];
    sort(G, G + 4);
    M[P][0] = M[P][1] = -2000000000;
    T[P][0] = T[P][1] = 0;
    for (int i = 0; i < 4; i++)
      for (int j = 0; j < 2; j++)
        if (M[P][j] == -2000000000 || M[P][j] == G[i].first) {
          M[P][j] = G[i].first;
          T[P][j] += G[i].second;
          break;
        }
  }
  void build(int P, int L, int R) {
    if (L == R) {
      M[P][1] = 2000000000;
      T[P][0] = 1;
      return;
    }
    int mid = (L + R) / 2;
    ;
    build((P * 2), L, mid);
    build((P * 2 + 1), mid + 1, R);
    updata(P);
  }
  void add(int P, int L, int R, int x, int y, int added) {
    if (L > y || R < x) return;
    if (L == x && R == y) {
      add_tag[P] += added;
      return;
    }
    int mid = (L + R) / 2;
    ;
    add((P * 2), L, mid, min(x, mid + 1), min(mid, y), added);
    add((P * 2 + 1), mid + 1, R, max(x, mid + 1), max(mid, y), added);
    updata(P);
  }
  int query(int P, int L, int R, int x, int y, int added) {
    added += add_tag[P];
    if (L > y || R < x) return 0;
    if (L == x && R == y) {
      int ret = 0;
      for (int i = 0; i < 2; i++)
        if (added + M[P][i] <= 2) ret += T[P][i];
      return ret;
    }
    int mid = (L + R) / 2;
    ;
    return query((P * 2), L, mid, min(x, mid + 1), min(mid, y), added) +
           query((P * 2 + 1), mid + 1, R, max(x, mid + 1), max(mid, y), added);
  }
} seg;
int main() {
  read(m);
  for (int i = 1; i <= m; i++) read(A[i]), pos[A[i]] = i;
  seg.build(1, 1, m);
  for (int i = 1; i <= m; i++) {
    int a1 = m + 1, a2 = m + 1;
    if (pos[i] > 1 && A[pos[i] - 1] < i) a1 = A[pos[i] - 1];
    if (pos[i] < m && A[pos[i] + 1] < i) a2 = A[pos[i] + 1];
    if (a1 > a2) swap(a1, a2);
    if (a1 == a2 && a1 == m + 1)
      seg.add(1, 1, m, 1, i, 1);
    else if (a2 == m + 1) {
      seg.add(1, 1, m, a1 + 1, i, 1);
    } else {
      seg.add(1, 1, m, 1, a1, -1);
      seg.add(1, 1, m, a2 + 1, i, 1);
    }
    ans += ((long long)seg.query(1, 1, m, 1, i, 0) - 1);
  }
  cout << ans << endl;
}
