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;
template <long long maxn>
struct sparse {
  long long logaritam[maxn + 1], st[maxn][25], rmq[maxn][25], k = 25;
  void init(vector<long long> a) {
    logaritam[1] = 0;
    for (long long i = 2; i < maxn; ++i) logaritam[i] = logaritam[i / 2] + 1;
    for (long long i = 0; i < a.size(); ++i) {
      st[i][0] = a[i];
      rmq[i][0] = a[i];
    }
    for (long long j = 1; j <= k; ++j) {
      for (long long i = 0; i + (1LL << j) <= a.size(); ++i) {
        st[i][j] = st[i][j - 1] + st[i + (1LL << (j - 1))][j - 1];
        rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1LL << (j - 1))][j - 1]);
      }
    }
  }
  long long sum(long long l, long long r) {
    long long sum = 0;
    for (long long j = k; j > -1; --j) {
      if ((1LL << j) <= r - l + 1) {
        sum += st[l][j];
        l += (1LL << j);
      }
    }
    return sum;
  }
  long long mini(long long L, long long R) {
    long long j = logaritam[R - L + 1];
    long long minimum = max(rmq[L][j], rmq[R - (1 << j) + 1][j]);
    return minimum;
  }
};
sparse<131072 * 4> tabla;
vector<long long> a;
long long binarnal(long long k, long long ind) {
  long long l = 0, r = ind, n = a.size();
  long long mid, sol = ind;
  while (l <= r) {
    mid = (l + r) / 2;
    long long x = tabla.mini(mid, ind);
    if (x == k) {
      sol = min(sol, mid);
      r = mid - 1;
    } else {
      l = mid + 1;
    }
  }
  return sol;
}
long long binarnar(long long k, long long ind) {
  long long l = ind, n = a.size(), r = n - 1;
  long long mid, sol = ind;
  while (l <= r) {
    mid = (l + r) / 2;
    long long x = tabla.mini(ind, mid);
    if (x == k) {
      sol = max(sol, mid);
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  return sol;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  cerr.tie(nullptr);
  long long n;
  cin >> n;
  vector<long long> p(n + 1);
  for (long long i = 0; i < n; ++i) {
    long long x;
    cin >> x;
    a.push_back(x);
    p[a[i]] = i;
  }
  tabla.init(a);
  long long sol = 0;
  for (long long i = 0; i < n; ++i) {
    long long r = binarnar(a[i], i);
    long long l = binarnal(a[i], i);
    if (l == r) continue;
    if (abs(l - i) > abs(r - i)) {
      for (long long j = i + 1; j <= r; ++j) {
        long long x = a[i] - a[j];
        if (p[x] < i && p[x] >= l) ++sol;
      }
    } else {
      for (long long j = l; j < i; ++j) {
        long long x = a[i] - a[j];
        if (p[x] > i && p[x] <= r) ++sol;
      }
    }
  }
  cout << sol << '\n';
}
