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;
inline long long read() {
  char ch = getchar();
  long long s = 0, w = 1;
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    s = s * 10 + ch - '0';
    ch = getchar();
  }
  return s * w;
}
int n, vis[200010], fa[200010], L[200010], R[200010], v[200010];
long long ans;
map<int, int> ma[200010];
pair<int, int> a[200010];
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
int main() {
  n = read();
  for (register int i = 1; i <= n; i++)
    a[i].first = v[i] = read(), a[i].second = i;
  sort(a + 1, a + n + 1);
  for (register int i = 1; i <= n; i++) L[i] = R[i] = fa[i] = i, ma[i][v[i]]++;
  for (register int i = 1; i <= n; i++) {
    int x = a[i].second;
    vis[x] = 1;
    if (i == 1) continue;
    if (!vis[x - 1]) {
      if (vis[x + 1])
        fa[x] = find(x + 1), ma[find(x + 1)][v[x]]++, L[find(x + 1)] = x;
      continue;
    }
    if (!vis[x + 1]) {
      if (vis[x - 1])
        fa[x] = find(x - 1), ma[find(x - 1)][v[x]]++, R[find(x - 1)] = x;
      ;
      continue;
    }
    int l = L[find(x - 1)], r = R[find(x + 1)];
    int p = l, q = x, t = find(x + 1);
    if (r - x <= x - l) p = x, q = r, t = find(x - 1);
    for (register int i = p; i <= q; i++) ans += ma[t][v[x] - v[i]];
    for (register int i = p; i <= q; i++)
      ma[t][v[i]]++, fa[i] = t, L[t] = min(L[t], i), R[t] = max(R[t], i);
  }
  printf("%lld\n", ans);
  return 0;
}
