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 <class T>
struct rge {
  T b, e;
};
template <class T>
rge<T> range(T i, T j) {
  return rge<T>{i, j};
};
template <class A, class B>
ostream &operator<<(ostream &os, pair<A, B> p) {
  return os << "(" << p.first << ", " << p.second << ")";
}
template <class T>
ostream &operator<<(ostream &os, rge<T> d) {
  os << "[";
  for (auto it = d.b; it != d.e; it++) os << (it == d.b ? "" : ", ") << *it;
  return os << "]";
}
const int N = 2e5 + 5;
const int LogN = 18;
int a[N], mp[N], lg[N];
int who[N][LogN];
int n;
int unite(int i, int j) { return a[i] > a[j] ? i : j; }
int qmax(int l, int r) {
  int k = lg[r - l + 1];
  return unite(who[l][k], who[r - (1 << k) + 1][k]);
}
bool in_range(int l, int r, int i) { return l <= i && i <= r; }
long long solve(int l, int r) {
  if (r - l + 1 <= 2) {
    return 0;
  }
  int pos = qmax(l, r);
  long long ans = solve(l, pos - 1) + solve(pos + 1, r);
  if (pos - l < r - pos) {
    for (int i = (l); i <= (pos - 1); i += (+1)) {
      if (in_range(pos + 1, r, mp[a[pos] - a[i]])) {
        ans++;
      }
    }
  } else {
    for (int i = (pos + 1); i <= (r); i += (+1)) {
      if (in_range(l, pos - 1, mp[a[pos] - a[i]])) {
        ans++;
      }
    }
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0), cout.precision(15);
  cin >> n;
  lg[0] = -1;
  for (int i = (1); i <= ((n)); i += (+1)) {
    cin >> a[i];
    lg[i] = lg[i >> 1] + 1;
    mp[a[i]] = i;
    who[i][0] = i;
  }
  for (int k = (1); k <= ((LogN - 1)); k += (+1)) {
    for (int l = (1); l <= ((n - (1 << k) + 1)); l += (+1)) {
      int r = l + (1 << (k - 1));
      who[l][k] = unite(who[l][k - 1], who[r][k - 1]);
    }
  }
  cout << solve(1, n) << '\n';
  return 0;
}
