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;
long long n, ans, num[200100], ls[200100], rs[200100], fa[200100], size[200100];
bool have[200100];
void get(long long now) {
  size[now] = 1;
  if (ls[now]) get(ls[now]), size[now] += size[ls[now]];
  if (rs[now]) get(rs[now]), size[now] += size[rs[now]];
}
void cle(long long now) {
  have[num[now]] = 0;
  if (ls[now]) cle(ls[now]);
  if (rs[now]) cle(rs[now]);
}
void add(long long now) {
  have[num[now]] = 1;
  if (ls[now]) add(ls[now]);
  if (rs[now]) add(rs[now]);
}
void calc(long long now, long long sum) {
  ans += have[sum - num[now]];
  if (ls[now]) calc(ls[now], sum);
  if (rs[now]) calc(rs[now], sum);
}
void dfs(long long now) {
  if (size[ls[now]] < size[rs[now]]) swap(ls[now], rs[now]);
  if (rs[now]) dfs(rs[now]), cle(rs[now]);
  if (ls[now]) {
    dfs(ls[now]);
    if (rs[now]) {
      calc(rs[now], num[now]);
      add(rs[now]);
    }
  }
  have[num[now]] = 1;
}
int main() {
  long long i, j, t, p;
  cin >> n;
  t = 0, num[t] = n + 1;
  for (i = 1; i <= n; i++) {
    scanf("%lld", &num[i]);
    for (p = 0; num[i] > num[t]; t = fa[t]) p = t;
    fa[p] = i, ls[i] = p, rs[t] = i, fa[i] = t;
    t = i;
  }
  get(rs[0]);
  dfs(rs[0]);
  cout << ans;
}
