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;
struct st1 {
  long long n, v;
};
long long a, b, c, N, M, t, ans, q[200007], p[200007];
long long fa[200007], l[200007], r[200007];
void sou(long long x1, long long nl, long long nr) {
  if (x1 <= (nl + nr) / 2) {
    for (int i = nl; i <= x1 - 1; i++)
      if (p[q[x1] - q[i]] > x1 && p[q[x1] - q[i]] <= nr) ans++;
  } else
    for (int i = x1 + 1; i <= nr; i++)
      if (p[q[x1] - q[i]] < x1 && p[q[x1] - q[i]] >= nl) ans++;
  if (l[x1]) sou(l[x1], nl, x1 - 1);
  if (r[x1]) sou(r[x1], x1 + 1, nr);
}
int main() {
  scanf("%I64d", &N);
  for (int i = 1; i <= N; i++) scanf("%I64d", &q[i]);
  for (int i = 1; i <= N; i++) p[q[i]] = i;
  a = 1;
  for (int i = 2; i <= N; i++) {
    if (q[i] < q[a])
      r[a] = i, fa[i] = a;
    else {
      while (fa[a] && q[i] > q[a]) a = fa[a];
      if (fa[a] == 0 && q[i] > q[a])
        fa[a] = i, l[i] = a;
      else {
        fa[r[a]] = i;
        l[i] = r[a];
        fa[i] = a;
        r[a] = i;
      }
    }
    a = i;
  }
  while (fa[a]) a = fa[a];
  sou(a, 1, N);
  printf("%I64d\n", ans);
  return 0;
}
