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 MAXN = 2e5 + 10;
int num[MAXN];
int L[MAXN], R[MAXN];
int idx[MAXN];
long long ans = 0;
int N;
void solve(int x) {
  bool flag = true;
  int tl, tr, tp;
  if (x - L[x] <= R[x] - x) {
    tl = L[x];
    tr = x - 1;
    flag = true;
  } else {
    tl = x + 1;
    tr = R[x];
    flag = false;
  }
  for (int i = tl; i <= tr; i++) {
    tp = num[x] - num[i];
    if (flag && idx[tp] > x && idx[tp] <= R[x])
      ans++;
    else if (!flag && idx[tp] < x && idx[tp] >= L[x])
      ans++;
  }
}
int main() {
  scanf("%d", &N);
  for (int i = 1; i <= N; i++) {
    scanf("%d", &num[i]);
    idx[num[i]] = i;
    L[i] = i;
    R[i] = i;
  }
  num[0] = num[N + 1] = N + 1;
  for (int i = 1; i <= N; i++) {
    while (num[L[i] - 1] <= num[i]) L[i] = L[L[i] - 1];
  }
  for (int i = N; i >= 1; i--) {
    while (num[R[i] + 1] <= num[i]) R[i] = R[R[i] + 1];
  }
  for (int i = 1; i <= N; i++) solve(i);
  printf("%I64d\n", ans);
  return 0;
}
