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>
std::vector<int> labels;
std::vector<int> sizes;
void Init(int n) {
  labels.resize(n + 1);
  sizes.resize(n + 1);
  for (int i = 1; i <= n; i++) {
    labels[i] = i;
    sizes[i] = 1;
  }
}
int Find(int a) {
  if (labels[a] == a) {
    return a;
  }
  int l = Find(labels[a]);
  labels[a] = l;
  return l;
}
void Union(int a, int b) {
  int l_a = Find(a);
  int l_b = Find(b);
  if (l_a == l_b) {
    return;
  }
  labels[l_a] = l_b;
  sizes[l_b] += sizes[l_a];
}
int main() {
  std::ios::sync_with_stdio(false);
  int n;
  std::cin >> n;
  Init(n);
  std::vector<int> p(n + 1), r(n + 1);
  for (int i = 1; i <= n; i++) {
    std::cin >> p[i];
    r[p[i]] = i;
  }
  int result = 0;
  for (int i = 1; i <= n; i++) {
    int idx = r[i];
    int left_size = 0, right_size = 0;
    int left_group = -1, right_group = -1;
    if (idx > 1 && p[idx - 1] < i) {
      left_group = Find(p[idx - 1]);
      left_size = sizes[left_group];
    }
    if (idx < n && p[idx + 1] < i) {
      right_group = Find(p[idx + 1]);
      right_size = sizes[right_group];
    }
    if (left_size < right_size) {
      for (int j = 1; j <= left_size; j++) {
        if (Find(i - p[idx - j]) == right_group) {
          ++result;
        }
      }
    } else {
      for (int j = 1; j <= right_size; j++) {
        if (Find(i - p[idx + j]) == left_group) {
          ++result;
        }
      }
    }
    if (left_group != -1) {
      Union(left_group, i);
    }
    if (right_group != -1) {
      Union(right_group, i);
    }
  }
  std::cout << result << '\n';
  return 0;
}
