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 = 100005;
void solve() {
  long long int n;
  cin >> n;
  long long int a[n];
  long long int left[n], right[n];
  long long int loc[n + 1];
  stack<long long int> s;
  for (long long int i = 0; i < n; i++) {
    left[i] = -1;
    cin >> a[i];
    loc[a[i]] = i;
    while (!s.empty() && a[s.top()] < a[i]) s.pop();
    if (!s.empty()) left[i] = s.top();
    s.push(i);
  }
  while (!s.empty()) s.pop();
  for (long long int i = n - 1; i >= 0; i--) {
    right[i] = n;
    while (!s.empty() && a[s.top()] < a[i]) s.pop();
    if (!s.empty()) right[i] = s.top();
    s.push(i);
  }
  long long int ans = 0;
  for (long long int i = 0; i < n; i++) {
    long long int l = left[i] + 1;
    long long int r = right[i] - 1;
    if (l < r) {
      long long int dis1 = i - l;
      long long int dis2 = r - i;
      if (dis1 <= dis2) {
        for (long long int j = l; j < i; j++) {
          long long int req = a[i] - a[j];
          if (loc[req] > i && loc[req] <= r) ans++;
        }
      } else {
        for (long long int j = i + 1; j <= r; j++) {
          long long int req = a[i] - a[j];
          if (loc[req] >= l && loc[req] < i) ans++;
        }
      }
    }
  }
  cout << ans << "\n";
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  srand(time(NULL));
  ;
  int t = 1;
  for (int i = 1; i <= t; i++) {
    solve();
  }
}
