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 = 2e5 + 5;
int ind[N];
template <typename T, class F = function<T(int i, int j, const vector<T> &t)>>
class SparseTable {
 public:
  int n;
  vector<T> a;
  vector<vector<T>> sp;
  F func;
  SparseTable(const vector<T> &_a, const F &f) : a(_a), func(f) {
    n = static_cast<int>(a.size());
    int max_log = 32 - __builtin_clz(n);
    sp.resize(max_log);
    sp[0].resize(n);
    iota(sp[0].begin(), sp[0].end(), 0);
    for (int j = 1; j < max_log; ++j) {
      sp[j].resize(n - (1 << j) + 1);
      for (int i = 0; i <= n - (1 << j); ++i) {
        sp[j][i] = func(sp[j - 1][i], sp[j - 1][i + (1 << (j - 1))], a);
      }
    }
  }
  T get(int l, int r) const {
    int lg = 32 - __builtin_clz(r - l + 1) - 1;
    return func(sp[lg][l], sp[lg][r - (1 << lg) + 1], a);
  }
};
int solve(int l, int r, const SparseTable<int> &sp, const vector<int> &v) {
  if (r < l) return 0;
  int max_ind = sp.get(l, r);
  int ans = solve(l, max_ind - 1, sp, v) + solve(max_ind + 1, r, sp, v);
  if (max_ind - l < r - max_ind) {
    for (int i = l; i < max_ind; i++) {
      int j = ind[v[max_ind] - v[i]];
      ans += j > max_ind && j <= r;
    }
  } else {
    for (int i = max_ind + 1; i <= r; i++) {
      int j = ind[v[max_ind] - v[i]];
      ans += j < max_ind && j >= l;
    }
  }
  return ans;
}
int main() {
  int n;
  scanf("%d", &n);
  vector<int> v(n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &v[i]);
    ind[v[i]] = i;
  }
  SparseTable<int> sp(v, [&](int i, int j, const vector<int> &v) {
    if (v[i] > v[j]) return i;
    return j;
  });
  printf("%d\n", solve(0, n - 1, sp, v));
}
