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 + 69;
int a[N], p[N];
unordered_set<int> s[N];
int dsu[N];
int find(int x) { return dsu[x] < 0 ? x : dsu[x] = find(dsu[x]); }
void merge(int a, int b) {
  a = find(a);
  b = find(b);
  if (a == b) return;
  dsu[a] = b;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  fill(dsu, dsu + N, -1);
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    p[a[i]] = i;
  }
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    int m = p[i];
    int l = find(m - 1);
    int r = find(m + 1);
    if (l > 0 && a[l] < a[m] && r <= n && a[r] < a[m]) {
      if (s[l].size() < s[r].size()) {
        merge(l, r);
        for (int x : s[l])
          if (s[r].count(a[m] - x)) ans++;
        s[r].insert(s[l].begin(), s[l].end());
        merge(m, r);
        s[r].insert(a[m]);
      } else {
        merge(r, l);
        for (int x : s[r])
          if (s[l].count(a[m] - x)) ans++;
        s[l].insert(s[r].begin(), s[r].end());
        merge(m, l);
        s[l].insert(a[m]);
      }
    } else if (l && a[l] < a[m]) {
      merge(m, l);
      s[l].insert(a[m]);
    } else if (r <= n && a[r] < a[m]) {
      merge(m, r);
      s[r].insert(a[m]);
    } else {
      s[m].insert(a[m]);
    }
  }
  cout << ans << '\n';
}
