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 = 300005, inf = 1e9 + 5;
const long long INF = 1e18 + 5;
const long double eps = 1e-9;
int ara[MAXN], pos[MAXN], tree[MAXN * 4];
int n;
void update(int cn, int l, int r, int pos, int val) {
  if (pos < l || pos > r) return;
  if (l == r) {
    tree[cn] = pos;
    return;
  }
  int m = (l + r) / 2;
  update(cn * 2, l, m, pos, val);
  update(cn * 2 + 1, m + 1, r, pos, val);
  if (ara[tree[cn * 2]] > ara[tree[cn * 2 + 1]]) {
    tree[cn] = tree[cn * 2];
  } else
    tree[cn] = tree[cn * 2 + 1];
}
int query(int cn, int l, int r, int x, int y) {
  if (y < l || x > r) return 0;
  if (l >= x && r <= y) return tree[cn];
  int m = (l + r) / 2, ll = cn * 2;
  int a = query(ll, l, m, x, y);
  int b = query(ll + 1, m + 1, r, x, y);
  if (ara[a] > ara[b])
    return a;
  else
    return b;
}
long long solve(int l, int r) {
  if (r - l <= 1) return 0;
  int ind = query(1, 1, n, l, r);
  int ans = 0;
  if (r - ind < ind - l) {
    for (int j = ind + 1; j <= r; j++) {
      int d = pos[ara[ind] - ara[j]];
      if (d >= l && d <= ind) {
        ans++;
      }
    }
  } else {
    for (int j = l; j < ind; j++) {
      int d = pos[ara[ind] - ara[j]];
      if (d >= ind && d <= r) {
        ans++;
      }
    }
  }
  return ans + solve(l, ind - 1) + solve(ind + 1, r);
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> ara[i];
    update(1, 1, n, i, ara[i]);
    pos[ara[i]] = i;
  }
  long long ans = solve(1, n);
  cout << ans << endl;
  return 0;
}
