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 const N = 200005;
int const LOGN = 21;
int f[N][LOGN];
int a[N];
int n;
struct node {
  int ls, rs;
  int l, r;
  int id;
} t[N];
int root, cnt = 0;
set<int> se[N];
int fc[N];
long long ans = 0;
int RMQ(int l, int r) {
  int k = 0;
  while (1 << (k + 1) <= r - l + 1) k++;
  int x = f[l][k], y = f[r - (1 << k) + 1][k];
  return a[x] > a[y] ? x : y;
}
void DP() {
  for (int i = 1; i <= n; i++) f[i][0] = i;
  for (int j = 1; (1 << j) <= n; j++)
    for (int i = 1; i + (1 << j) - 1 <= n; i++) {
      int x = f[i][j - 1], y = f[i + (1 << (j - 1))][j - 1];
      f[i][j] = a[x] > a[y] ? x : y;
    }
}
int build(int l, int r) {
  if (l > r) return 0;
  int ret = ++cnt;
  t[cnt].l = l;
  t[cnt].r = r;
  int pos = RMQ(l, r);
  t[cnt].id = pos;
  if (l == r) return ret;
  t[ret].ls = build(l, pos - 1);
  t[ret].rs = build(pos + 1, r);
  return ret;
}
void dfs(int x) {
  if (t[x].l == t[x].r) {
    fc[x] = x;
    se[x].insert(a[t[x].id]);
    return;
  }
  int lse = 0, rse = 0;
  if (t[x].ls) {
    dfs(t[x].ls);
    lse = fc[t[x].ls];
  }
  if (t[x].rs) {
    dfs(t[x].rs);
    rse = fc[t[x].rs];
  }
  if (lse && rse) {
    if (((int)(se[lse]).size()) > ((int)(se[rse]).size())) swap(lse, rse);
    for (auto c : se[lse]) {
      if (se[rse].count(a[t[x].id] - c)) ++ans;
    }
    for (auto c : se[lse]) se[rse].insert(c);
    se[lse].clear();
    se[rse].insert(a[t[x].id]);
    fc[x] = rse;
    return;
  }
  if (lse) {
    se[lse].insert(a[t[x].id]);
    fc[x] = lse;
    return;
  }
  if (rse) {
    se[rse].insert(a[t[x].id]);
    fc[x] = rse;
    return;
  }
}
int main() {
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  DP();
  root = build(1, n);
  dfs(root);
  cout << ans << '\n';
}
