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 MAXN = 212345;
int n;
int v[MAXN];
int inv[MAXN];
pair<int, int> st[4 * MAXN];
void build(int nd, int l, int r) {
  if (l == r) {
    st[nd] = make_pair(v[l], l);
    return;
  }
  int mid = (l + r) >> 1;
  int nxt = nd << 1;
  build(nxt, l, mid);
  build(nxt + 1, mid + 1, r);
  if (st[nxt].first > st[nxt + 1].first)
    st[nd] = st[nxt];
  else
    st[nd] = st[nxt + 1];
}
pair<int, int> query(int nd, int l, int r, int ll, int rr) {
  if (rr < l || r < ll) return make_pair(-1, -1);
  if (ll <= l && r <= rr) return st[nd];
  int mid = (l + r) >> 1;
  int nxt = nd << 1;
  pair<int, int> q1 = query(nxt, l, mid, ll, rr);
  pair<int, int> q2 = query(nxt + 1, mid + 1, r, ll, rr);
  if (q1.first > q2.first)
    return q1;
  else
    return q2;
}
int ans;
void solve(int l, int r) {
  if (r - l < 2) return;
  int p = query(1, 0, n - 1, l, r).second;
  int x = v[p];
  int s1 = p - l;
  int s2 = r - p;
  if (s1 < s2) {
    for (int i = p - 1; i >= l; --i) {
      int op = inv[x - v[i]];
      if (p <= op && op <= r) ++ans;
    }
  } else {
    for (int i = p + 1; i <= r; ++i) {
      int op = inv[x - v[i]];
      if (l <= op && op <= p) ++ans;
    }
  }
  solve(l, p - 1);
  solve(p + 1, r);
}
int main() {
  cin >> n;
  for (int i = 0; i < n; ++i) {
    scanf("%d", v + i);
    inv[v[i]] = i;
  }
  build(1, 0, n - 1);
  solve(0, n - 1);
  cout << ans << endl;
  return 0;
}
