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 = 5e5 + 5;
const int MOD = 1e9 + 7;
long long ans = 0;
int n;
int a[N], pos[N];
int t[4 * N];
void build(int v, int l, int r) {
  if (l == r) {
    t[v] = a[l];
    return;
  }
  int m = (l + r) >> 1;
  build(2 * v, l, m);
  build(2 * v + 1, m + 1, r);
  t[v] = max(t[2 * v], t[2 * v + 1]);
}
long long get(int v, int tl, int tr, int l, int r) {
  if (l <= tl && tr <= r) {
    return t[v];
  }
  int tm = (tl + tr) >> 1;
  if (r <= tm) return get(2 * v, tl, tm, l, r);
  if (l > tm) return get(2 * v + 1, tm + 1, tr, l, r);
  return max(get(2 * v, tl, tm, l, r), get(2 * v + 1, tm + 1, tr, l, r));
}
void calc(int l, int r, int ps) {
  if (l >= r) return;
  if (ps - l < r - ps) {
    for (int i = l; i < ps; ++i) {
      int s = a[ps] - a[i];
      if (ps < pos[s] && pos[s] <= r) ans++;
    }
  } else {
    for (int i = ps + 1; i <= r; ++i) {
      int s = a[ps] - a[i];
      if (l <= pos[s] && pos[s] < ps) ans++;
    }
  }
  if (l < ps) calc(l, ps - 1, pos[get(1, 0, n - 1, l, ps - 1)]);
  if (r > ps) calc(ps + 1, r, pos[get(1, 0, n - 1, ps + 1, r)]);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    pos[a[i]] = i;
  }
  build(1, 0, n - 1);
  calc(0, n - 1, pos[get(1, 0, n - 1, 0, n - 1)]);
  cout << ans;
  return 0;
}
