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;
int n, p[210000], lson[210000], rson[210000];
long long ans;
pair<int, int> e[4 * 210000];
set<int> s[210000];
void build(int x, int l, int r) {
  if (l == r) {
    e[x] = pair<int, int>(p[l], l);
    return;
  }
  int mid = (l + r) / 2;
  build(x * 2, l, mid);
  build(x * 2 + 1, mid + 1, r);
  e[x] = max(e[x * 2], e[x * 2 + 1]);
}
pair<int, int> ask(int x, int l, int r, int ls, int rs) {
  if (ls <= l && r <= rs) return e[x];
  if (ls > r || rs < l) return pair<int, int>(0, 0);
  int mid = (l + r) / 2;
  return max(ask(x * 2, l, mid, ls, rs), ask(x * 2 + 1, mid + 1, r, ls, rs));
}
void calc(int x, int l, int r) {
  int k = 0;
  if (l < x) {
    lson[x] = ask(1, 1, n, l, x - 1).second;
    calc(lson[x], l, x - 1);
    k = lson[x];
  }
  if (x < r) {
    rson[x] = ask(1, 1, n, x + 1, r).second;
    calc(rson[x], x + 1, r);
    if (r - x > k) k = rson[x];
  }
  if (k) s[x].swap(s[k]);
  s[x].insert(p[x]);
  int ls, rs;
  if (k == lson[x])
    ls = x, rs = r;
  else
    ls = l, rs = x;
  for (int i = ls; i <= rs; i++) {
    if (s[x].find(p[x] - p[i]) != s[x].end()) ans++;
  }
  for (int i = ls; i <= rs; i++) s[x].insert(p[i]);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &p[i]);
  build(1, 1, n);
  calc(ask(1, 1, n, 1, n).second, 1, n);
  printf("%lld", ans);
  return 0;
}
