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;
long long res, a[200005], ip[200005], rmq[200005][18];
long long lg[200005];
int q(int l, int r) {
  int po = lg[r - l + 1];
  return max(rmq[l][po], rmq[r - (1 << po) + 1][po]);
}
void solve(int p, int l, int r) {
  if (p == l && p == r) return;
  if (p == l || p == r) {
    if (p == l) solve(ip[q(l + 1, r)], l + 1, r);
    if (p == r) solve(ip[q(l, r - 1)], l, r - 1);
    return;
  }
  int ini = l, fin = p - 1, fi = p + 1, ff = r;
  if (r - p < p - l) {
    swap(ini, fi);
    swap(fin, ff);
  }
  for (int i = ini; i <= fin; i++)
    if (ip[a[p] - a[i]] >= fi && ip[a[p] - a[i]] <= ff) res++;
  solve(ip[q(fi, ff)], fi, ff);
  solve(ip[q(ini, fin)], ini, fin);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  lg[0] = -1;
  for (int i = 1; i < 200005; i++) lg[i] = (lg[i - 1] + !(i & (i - 1)));
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    ip[a[i]] = i;
  }
  for (int i = 0; i < n; i++) rmq[i][0] = a[i];
  for (int i = 1; i <= lg[n]; i++)
    for (int j = 0; j + (1 << i) <= n; j++)
      rmq[j][i] = max(rmq[j][i - 1], rmq[j + (1 << (i - 1))][i - 1]);
  solve(ip[n], 0, n - 1);
  cout << (res) << '\n';
  return 0;
}
