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;
long long p[2 * 100000 + 5], n;
long long tree[8 * 100000 + 5];
long long m[2 * 100000 + 5];
void build_tree(long long curr, long long l, long long r) {
  if (l > r) return;
  if (l == r) {
    tree[curr] = l;
    return;
  }
  long long mid = (l + r) / 2;
  build_tree(2 * curr, l, mid);
  build_tree(2 * curr + 1, mid + 1, r);
  if (p[tree[2 * curr]] >= p[tree[2 * curr + 1]])
    tree[curr] = tree[2 * curr];
  else
    tree[curr] = tree[2 * curr + 1];
}
long long RMQ(long long curr, long long l, long long r, long long L,
              long long R) {
  if (l > r || l > R || r < L) return 0;
  if (L <= l && r <= R) return tree[curr];
  long long mid = (l + r) / 2;
  long long idxL = RMQ(2 * curr, l, mid, L, R);
  long long idxR = RMQ(2 * curr + 1, mid + 1, r, L, R);
  if (p[idxL] >= p[idxR])
    return idxL;
  else
    return idxR;
}
long long sol(long long l, long long r) {
  if (r - l < 2) return 0;
  long long midx = RMQ(1, 1, n, l, r);
  long long ans = 0;
  if (midx - l < r - midx) {
    for (int i = l; i < midx; ++i) {
      if (m[p[midx] - p[i]] > midx && m[p[midx] - p[i]] <= r) ans++;
    }
  } else {
    for (int i = midx + 1; i <= r; ++i) {
      if (m[p[midx] - p[i]] < midx && m[p[midx] - p[i]] >= l) ans++;
    }
  }
  return ans + sol(l, midx - 1) + sol(midx + 1, r);
}
int main() {
  scanf("%lld", &n);
  for (long long i = 1; i <= n; ++i) {
    scanf("%lld", &p[i]);
    m[p[i]] = i;
  }
  p[0] = 0;
  build_tree(1, 1, n);
  printf("%lld\n", sol(1, n));
  return 0;
}
