#include <bits/stdc++.h>
using namespace std;
struct st {
  int v1[1200011], c1[1200011], v2[1200011], c2[1200011], l[1200011],
      r[1200011], add[1200011];
  void build(int L, int R, int k = 1) {
    l[k] = L;
    r[k] = R;
    v1[k] = v2[k] = c2[k] = add[k] = 0;
    c1[k] = R - L + 1;
    if (L == R) return;
    build(L, (L + R) >> 1, k + k);
    build(((L + R) >> 1) + 1, R, k + k + 1);
  }
  inline void push_down(int k) {
    if (add[k] == 0) return;
    if (l[k] != r[k]) add[k + k] += add[k], add[k + k + 1] += add[k];
    v1[k] += add[k];
    v2[k] += add[k];
    add[k] = 0;
  }
  inline void update(int k) {
    if (l[k] == r[k]) return;
    push_down(k + k);
    push_down(k + k + 1);
    v1[k] = v1[k + k];
    c1[k] = c1[k + k];
    v2[k] = v2[k + k];
    c2[k] = c2[k + k];
    if (c1[k + k + 1] != 0) {
      if (c1[k] == 0 || v1[k + k + 1] < v1[k])
        v2[k] = v1[k], c2[k] = c1[k], v1[k] = v1[k + k + 1],
        c1[k] = c1[k + k + 1];
      else if (v1[k + k + 1] == v1[k])
        c1[k] += c1[k + k + 1];
      else if (c2[k] == 0 || v1[k + k + 1] < v2[k])
        v2[k] = v1[k + k + 1], c2[k] = c1[k + k + 1];
      else if (v1[k + k + 1] == v2[k])
        c2[k] += c1[k + k + 1];
    }
    if (c2[k + k + 1] != 0) {
      if (c2[k] == 0 || v2[k + k + 1] < v2[k])
        v2[k] = v2[k + k + 1], c2[k] = c2[k + k + 1];
      else if (v2[k + k + 1] == v2[k])
        c2[k] += c2[k + k + 1];
    }
  }
  int query(int k = 1) {
    push_down(k);
    return (v1[k] <= 2 ? c1[k] : 0) + (v2[k] <= 2 ? c2[k] : 0);
  }
  inline void insert(int L, int R, int va, int k = 1) {
    push_down(k);
    if (l[k] >= L && r[k] <= R) {
      add[k] += va;
      return;
    }
    if (r[k + k] >= L) insert(L, R, va, k + k);
    if (l[k + k] <= R) insert(L, R, va, k + k + 1);
    update(k);
  }
} f;
int n, x[300011], y[300011];
inline int value(int a, int b, int c) { return (b < a) + (b < c) - 1; }
void init() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &x[i]);
    y[x[i]] = i;
  }
  f.build(1, n);
  x[0] = x[n + 1] = 0x7fffffff;
  for (int i = 1; i <= n; ++i)
    f.insert(x[i], n, value(x[i - 1], x[i], x[i + 1]));
}
long long ans(0);
void work() {
  for (int i = 1; i < n; ++i) {
    ans += f.query() - i;
    f.insert(i + 1, n, -value(x[y[i] - 1], i, x[y[i] + 1]));
    x[y[i]] = 0x7fffffff;
    if (x[y[i] + 1] != 0x7fffffff) f.insert(x[y[i] + 1], n, 1);
    if (x[y[i] - 1] != 0x7fffffff) f.insert(x[y[i] - 1], n, 1);
  }
  cout << ans << endl;
}
int main() {
  init();
  work();
  return 0;
}
