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 sz = 2e5 + 10;
int ar[sz], p[sz], n, dot[sz * 4];
void build(int nu, int l, int r) {
  if (l == r)
    dot[nu] = ar[l];
  else {
    int mid = (l + r) >> 1;
    build(nu * 2, l, mid);
    build(nu * 2 + 1, mid + 1, r);
    dot[nu] = max(dot[nu * 2], dot[nu * 2 + 1]);
  }
}
int lg, rg;
int que(int nu, int l, int r) {
  if (l >= lg and r <= rg)
    return dot[nu];
  else if (l > rg or r < lg)
    return -1;
  else {
    int mid = (l + r) >> 1;
    return max(que(nu * 2, l, mid), que(nu * 2 + 1, mid + 1, r));
  }
}
int an = 0;
void dfs(int l, int r) {
  lg = l, rg = r;
  int x = que(1, 0, n - 1);
  if (p[x] - l < r - p[x]) {
    for (int a = l; a < p[x]; a++) {
      if (p[x - ar[a]] > p[x] and p[x - ar[a]] <= r) an++;
    }
  } else {
    for (int a = p[x] + 1; a <= r; a++) {
      if (p[x - ar[a]] >= l and p[x - ar[a]] < p[x]) an++;
    }
  }
  if (p[x] != l) dfs(l, p[x] - 1);
  if (p[x] != r) dfs(p[x] + 1, r);
}
int main() {
  cin >> n;
  for (int a = 0; a < n; a++) {
    scanf("%d", &ar[a]);
    p[ar[a]] = a;
  }
  build(1, 0, n - 1);
  dfs(0, n - 1);
  cout << an;
}
