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 n;
long long a[200005];
long long rec(long long l, long long r) {
  if (r - l <= 1) {
    return 0;
  }
  long long mid = (l + r) / 2;
  long long ans = 0;
  ans += rec(l, mid);
  ans += rec(mid + 1, r);
  set<long long> L, R;
  long long maxval = 0, ptr = mid;
  for (long long i = (long long)(mid); i >= (long long)(l); i--) {
    maxval = max(maxval, a[i]);
    while (ptr + 1 <= r && a[ptr + 1] < maxval) {
      ptr++;
      R.insert(a[ptr]);
    }
    long long x = maxval - a[i];
    ans += R.count(x);
  }
  maxval = 0;
  ptr = mid + 1;
  for (long long i = (long long)(mid + 1); i <= (long long)(r); i++) {
    maxval = max(maxval, a[i]);
    while (ptr - 1 >= l && a[ptr - 1] < maxval) {
      ptr--;
      L.insert(a[ptr]);
    }
    long long x = maxval - a[i];
    ans += L.count(x);
  }
  return ans;
}
int main() {
  cin >> n;
  for (long long i = (long long)(1); i <= (long long)(n); i++) cin >> a[i];
  cout << rec(1, n);
}
