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 ull = unsigned long long;
using ll = long long;
const int N = 200005, MOD = 1e9 + 7;
int n, p[N], rt[N], cnt[N];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> p[i];
  }
  stack<int> s;
  for (int i = n - 1; i >= 0; --i) {
    while (!s.empty() && p[i] > p[s.top()]) {
      s.pop();
    }
    if (s.empty())
      rt[i] = n;
    else
      rt[i] = s.top();
    s.push(i);
  }
  while (!s.empty()) s.pop();
  ll ans = 0;
  for (int i = 0; i < n; ++i) {
    while (!s.empty() && p[i] > p[s.top()]) {
      s.pop();
    }
    int lf = -1;
    if (!s.empty()) lf = s.top();
    if (lf < i - 1 && rt[i] > i + 1) {
      for (int j = rt[i] - 1; j > i; --j) {
        ++cnt[p[j]];
      }
      for (int j = lf + 1; j < i; ++j) {
        ans += cnt[p[i] - p[j]];
      }
      for (int j = rt[i] - 1; j > i; --j) {
        --cnt[p[j]];
      }
    }
    s.push(i);
  }
  cout << ans << '\n';
  return 0;
}
