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 N = 2e5 + 7;
int Log[N], bin[21], ls[N], rs[N], root, a[N], n, i, j;
set<int> s[N];
pair<int, int> mx[N][20];
long long ans;
void merge(int x, int y) {
  if (s[x].size() < s[y].size()) swap(s[x], s[y]);
  for (auto& z : s[y]) s[x].insert(z);
  s[y].clear();
}
void dfs(int x) {
  if (!x) return;
  dfs(ls[x]);
  dfs(rs[x]);
  if (s[ls[x]].size() > s[rs[x]].size()) swap(ls[x], rs[x]);
  for (auto& z : s[ls[x]])
    if (s[rs[x]].count(a[x] - z)) ans++;
  s[x].insert(a[x]);
  merge(x, ls[x]);
  merge(x, rs[x]);
}
int query(int l, int r) {
  int t = Log[r - l + 1];
  return max(mx[l][t], mx[r - bin[t] + 1][t]).second;
}
int build(int l, int r) {
  if (l > r) return 0;
  int x = query(l, r);
  ls[x] = build(l, x - 1);
  rs[x] = build(x + 1, r);
  return x;
}
int main() {
  for (scanf("%d", &n), i = 1; i <= n; ++i) scanf("%d", a + i);
  for (Log[0] = -1, i = 1; i <= n; ++i) Log[i] = Log[i >> 1] + 1;
  for (bin[0] = 1, i = 1; i < 20; ++i) bin[i] = bin[i - 1] << 1;
  for (i = 1; i <= n; ++i) mx[i][0] = pair<int, int>(a[i], i);
  for (j = 1; j <= Log[n]; ++j)
    for (i = 1; i + bin[j - 1] <= n; ++i)
      mx[i][j] = max(mx[i][j - 1], mx[i + bin[j - 1]][j - 1]);
  root = build(1, n);
  dfs(root);
  printf("%d\n", ans);
}
