#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10, SQ = 2000, BL = N / SQ + 10, M = 2;
int cnt[BL][N], lazy[N], a[N];
int p[N], last[N];
void add(int l, int r, int d) {
  while (l % SQ != 0 && l < r) {
    cnt[l / SQ][a[l]]--;
    a[l] += d;
    cnt[l / SQ][a[l]]++;
    l++;
  }
  while (r % SQ != 0 && l < r) {
    cnt[(r - 1) / SQ][a[r - 1]]--;
    a[r - 1] += d;
    cnt[(r - 1) / SQ][a[r - 1]]++;
    r--;
  }
  for (int i = l / SQ; i < r / SQ; i++) lazy[i] += d;
  return;
}
int get(int l, int r) {
  int res = 0;
  while (l % SQ != 0 && l < r) {
    if (a[l] + lazy[l / SQ] <= M) res++;
    l++;
  }
  while (r % SQ != 0 && l < r) {
    if (a[r - 1] + lazy[(r - 1) / SQ] <= M) res++;
    r--;
  }
  for (int i = l / SQ; i < r / SQ; i++) {
    for (int j = 0; j <= M; j++)
      if (j >= lazy[i]) res += cnt[i][j - lazy[i]];
  }
  return res;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    --x;
    p[x] = i;
  }
  for (int i = 0; i < n; i++) cnt[i / SQ][0]++;
  memset(last, -1, sizeof last);
  long long ans = 0;
  for (int r = 0; r < n; r++) {
    int v = p[r];
    add(last[v + 1] + 1, r + 1, 1);
    if (v) add(0, last[v - 1] + 1, -1);
    ans += get(0, r);
    last[v] = r;
  }
  cout << ans << endl;
}
