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>
const int N = (int)2e5 + 7;
const int inf = (int)1e9 + 7;
const int mod = (int)1e9 + 7;
const long long linf = (long long)1e18 + 7;
const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
using namespace std;
int n;
int a[N], pos[N], lg[N];
int st[20][N];
int opt(int x, int y) {
  if (a[x] > a[y]) return x;
  return y;
}
int mx(int l, int r) {
  int dg = lg[r - l + 1];
  return opt(st[dg][l], st[dg][r - (1 << dg) + 1]);
}
long long ans;
void solve(int l = 1, int r = n) {
  if (l > r) return;
  int mid = mx(l, r);
  solve(l, mid - 1);
  solve(mid + 1, r);
  int mx = a[mid];
  if (mid - l < r - mid) {
    for (int i = (l); i <= (mid - 1); i++) {
      int j = pos[mx - a[i]];
      if (j > mid && j <= r && j != i) ++ans;
    }
  } else {
    for (int i = (mid + 1); i <= (r); i++) {
      int j = pos[mx - a[i]];
      if (l <= j && j < mid && j != i) {
        ++ans;
      }
    }
  }
}
int main() {
  ios_base ::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  for (int i = (1); i <= (n); i++) {
    cin >> a[i];
    pos[a[i]] = i;
    st[0][i] = i;
  }
  for (int i = (2); i <= (n); i++) lg[i] = lg[i >> 1] + 1;
  for (int dg = (1); dg <= (lg[n]); dg++) {
    for (int i = (1); i <= (n); i++) {
      if (i + (1 << dg) - 1 > n) break;
      st[dg][i] = opt(st[dg - 1][i], st[dg - 1][i + (1 << (dg - 1))]);
    }
  }
  solve();
  cout << ans;
  exit(0);
}
