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;
const int maxn = 2e5 + 10;
int n, l[maxn], r[maxn], a[maxn], stk[maxn];
bool vis[maxn];
unordered_set<int> s[maxn];
int ans;
int build() {
  int top = 0;
  for (int i = 1; i <= n; i++) l[i] = r[i] = vis[i] = 0;
  for (int i = 1; i <= n; i++) {
    int k = top;
    while (k > 0 && a[stk[k - 1]] < a[i]) --k;
    if (k) r[stk[k - 1]] = i;
    if (k < top) l[i] = stk[k];
    stk[k++] = i;
    top = k;
  }
  for (int i = 1; i <= n; i++) vis[l[i]] = vis[r[i]] = 1;
  int ret = 0;
  for (int i = 1; i <= n; i++)
    if (vis[i] == 0) ret = i;
  return ret;
}
void dfs(int x) {
  if (!x) return;
  dfs(l[x]);
  dfs(r[x]);
  if (s[l[x]].size() > s[r[x]].size()) swap(s[l[x]], s[r[x]]);
  for (auto v : s[l[x]]) ans += s[r[x]].count(a[x] - v);
  swap(s[r[x]], s[x]);
  for (auto v : s[l[x]]) s[x].insert(v);
  s[l[x]].clear();
  s[x].insert(a[x]);
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  int rt = build();
  dfs(rt);
  cout << ans << endl;
  return 0;
}
