#include <bits/stdc++.h>
void Get(int &T) {
  char C;
  bool F = 0;
  for (; C = getchar(), C < '0' || C > '9';)
    if (C == '-') F = 1;
  for (T = C - '0'; C = getchar(), C >= '0' && C <= '9'; T = T * 10 + C - '0')
    ;
  F && (T = -T);
}
int N, M;
int A[400005];
int B[400005];
int Min[400005];
int Belong[400005];
int Offset[400005];
int Cnt1[400005];
int Cnt2[400005];
void Repair(int k) {
  Min[k] = 0x2f2f2f2f;
  for (int i = (k - 1) * M + 1; i <= k * M; i++) {
    B[i] += Offset[k];
    if (Min[k] > B[i]) Min[k] = B[i];
  }
  Offset[k] = 0;
  Cnt1[k] = Cnt2[k] = 0;
  for (int i = (k - 1) * M + 1; i <= k * M; i++) {
    Cnt1[k] += (B[i] == Min[k]);
    Cnt2[k] += (B[i] == Min[k] + 1);
  }
}
void Add(int X, int k) {
  for (int i = X; i <= Belong[X] * M; i++) {
    B[i] += k;
  }
  Repair(Belong[X]);
  for (int i = Belong[X] + 1; i <= M; i++) {
    Offset[i] += k;
  }
}
int Ask(int X) {
  int Ans = 0;
  for (int i = X; i <= Belong[X] * M; i++) {
    if (B[i] + Offset[Belong[X]] == 1) Ans++;
    if (B[i] + Offset[Belong[X]] == 2) Ans++;
  }
  for (int i = Belong[X] + 1; i <= M; i++) {
    if (Offset[i] + Min[i] == 1) {
      Ans += Cnt1[i];
      Ans += Cnt2[i];
    } else if (Offset[i] + Min[i] == 2) {
      Ans += Cnt1[i];
    }
  }
  return Ans;
}
void Init() {
  Get(N);
  M = ceil(sqrt(N));
  A[0] = A[N + 1] = 0x2f2f2f2f;
  for (int i = 1; i <= N; i++) Get(A[i]);
}
int Order[400005];
long long Ans;
void Work() {
  for (int k = 1, i; k <= N; k++) {
    i = A[k];
    B[i] = 1 - (A[k] > A[k - 1]) - (A[k] > A[k + 1]);
  }
  for (int i = 1; i <= N; i++) B[i] += B[i - 1];
  for (int i = N + 1; i <= M * M; i++) B[i] = 0x2f2f2f2f;
  memset(Min, 0x2f, sizeof Min);
  for (int i = 1; i <= M * M; i++) Belong[i] = ((i - 1) / M) + 1;
  for (int i = 1; i <= M; i++) Repair(i);
  for (int i = 1; i <= N; i++) {
    Order[A[i]] = i;
  }
  for (int k = 1, i; k <= N; k++) {
    i = Order[k];
    Ans += Ask(A[i]);
    Add(A[i], -1);
    if (A[i + 1] < 0x2f2f2f2f) Add(A[i + 1], 1);
    if (A[i - 1] < 0x2f2f2f2f) Add(A[i - 1], 1);
    A[i] = 0x2f2f2f2f;
  }
  Ans -= N;
}
void Output() { printf("%I64d\n", Ans); }
int main() {
  Init();
  Work();
  Output();
  return 0;
}
