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;
using LL = long long;
class RMQ {
 public:
  RMQ(int _n) {
    n = _n;
    logn = log2(n) + 1;
    x = vector<int>(n);
    f = vector<vector<int>>(n, vector<int>(logn));
  }
  void Build() {
    for (int i = 0; i < n; ++i) f[i][0] = i;
    for (int j = 1; (1 << j) <= n; ++j) {
      for (int i = 0; i + (1 << j) - 1 < n; ++i) {
        if (x[f[i][j - 1]] > x[f[i + (1 << (j - 1))][j - 1]]) {
          f[i][j] = f[i][j - 1];
        } else {
          f[i][j] = f[i + (1 << (j - 1))][j - 1];
        }
      }
    }
  }
  int Query(int a, int b) {
    if (a > b) swap(a, b);
    int k = log2(b - a + 1);
    if (x[f[a][k]] > x[f[b + 1 - (1 << k)][k]]) {
      return f[a][k];
    } else {
      return f[b + 1 - (1 << k)][k];
    }
  }
  int n, logn;
  vector<int> x;
  vector<vector<int>> f;
};
LL ans = 0;
vector<int> x;
void Solve(int l, int r, set<int>& s, RMQ& rmq) {
  if (s.size() <= 1) return;
  int p = rmq.Query(l, r);
  if (p - l > r - p) {
    set<int> other;
    for (int i = r; i > p; --i) {
      s.erase(x[i]);
      other.insert(x[i]);
    }
    s.erase(x[p]);
    for (int i : other) {
      if (s.find(x[p] - i) != s.end()) ++ans;
    }
    Solve(l, p - 1, s, rmq);
    Solve(p + 1, r, other, rmq);
  } else {
    set<int> other;
    for (int i = l; i < p; ++i) {
      s.erase(x[i]);
      other.insert(x[i]);
    }
    s.erase(x[p]);
    for (int i : other) {
      if (s.find(x[p] - i) != s.end()) ++ans;
    }
    Solve(l, p - 1, other, rmq);
    Solve(p + 1, r, s, rmq);
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  x = vector<int>(n);
  RMQ rmq(n);
  set<int> s;
  for (int i = 0; i < n; ++i) {
    cin >> x[i];
    s.insert(x[i]);
    rmq.x[i] = x[i];
  }
  rmq.Build();
  Solve(0, n - 1, s, rmq);
  cout << ans << endl;
  return 0;
}
