You are given a permutation p of n integers 1, 2, ..., n (a permutation is an array where each element from 1 to n occurs exactly once).

Let's call some subsegment p[l, r] of this permutation special if p_l + p_r = max _{i = l}^{r} p_i. Please calculate the number of special subsegments.

Input

The first line contains one integer n (3 ≤ n ≤ 2 ⋅ 10^5).

The second line contains n integers p_1, p_2, ..., p_n (1 ≤ p_i ≤ n). All these integers are pairwise distinct.

Output

Print the number of special subsegments of the given permutation.

Examples

Input


5
3 4 1 5 2


Output


2


Input


3
1 3 2


Output


1

Note

Special subsegments in the first example are [1, 5] and [1, 3].

The only special subsegment in the second example is [1, 3].
#include <bits/stdc++.h>
using namespace std;
const int N = 200000 + 77, L = 18;
int n, A, P[N], R[N], Mx[N][L], LG[N];
inline int GetMax(int le, int ri) {
  int t = LG[ri - le + 1];
  return max(Mx[le][t], Mx[ri - (1 << t) + 1][t]);
}
void Solve(int le = 1, int ri = n) {
  if (ri <= le) return;
  int X = GetMax(le, ri);
  int Y = R[X];
  if (Y - le <= ri - Y) {
    for (int i = le; i < Y; ++i)
      if (R[X - P[i]] > Y && R[X - P[i]] <= ri) ++A;
  } else {
    for (int i = Y + 1; i <= ri; ++i)
      if (R[X - P[i]] < Y && R[X - P[i]] >= le) ++A;
  }
  Solve(le, Y - 1);
  Solve(Y + 1, ri);
}
int main() {
  for (int i = 2; i < N; ++i) LG[i] = LG[i >> 1] + 1;
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", P + i), R[P[i]] = i, Mx[i][0] = P[i];
  for (int j = 1; j < L; ++j)
    for (int i = 1; i <= n; ++i) {
      Mx[i][j] = Mx[i][j - 1];
      int p = i + (1 << (j - 1));
      if (p <= n && Mx[p][j - 1] > Mx[i][j]) Mx[i][j] = Mx[p][j - 1];
    }
  Solve();
  printf("%d\n", A);
  return 0;
}
