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 segment_tree[200005 * 4];
int P[200005];
int pos[200005];
set<int> S[200005];
vector<int> Graph[200005];
int set_index[200005];
set<int>::iterator it;
long long ans;
void build(int index, int l, int r) {
  if (l == r) {
    segment_tree[index] = P[l];
    return;
  }
  int m = (l + r) / 2;
  build(index * 2, l, m);
  build(index * 2 + 1, m + 1, r);
  segment_tree[index] =
      max(segment_tree[index * 2], segment_tree[index * 2 + 1]);
}
int query(int index, int l, int r, int L, int R) {
  if (L > r || R < l) return 0;
  if (L <= l && r <= R) {
    return segment_tree[index];
  }
  int m = (l + r) / 2;
  int f = query(index * 2, l, m, L, R);
  int s = query(index * 2 + 1, m + 1, r, L, R);
  return max(f, s);
}
void cartesian_tree(int l, int r, int n, int parent = 0) {
  int root = query(1, 0, n - 1, l, r);
  if (parent) Graph[parent].push_back(root);
  if (pos[root] > l) cartesian_tree(l, pos[root] - 1, n, root);
  if (pos[root] < r) cartesian_tree(pos[root] + 1, r, n, root);
}
void dfs(int node) {
  if (Graph[node].size() == 0) {
    S[node].insert(node);
    set_index[node] = node;
  } else if (Graph[node].size() == 1) {
    dfs(Graph[node][0]);
    S[set_index[Graph[node][0]]].insert(node);
    set_index[node] = set_index[Graph[node][0]];
  } else {
    dfs(Graph[node][0]);
    dfs(Graph[node][1]);
    int current, ss, big = set_index[Graph[node][0]],
                     small = set_index[Graph[node][1]];
    if (S[small].size() > S[big].size()) swap(big, small);
    ss = S[big].size();
    for (it = S[small].begin(); it != S[small].end(); ++it) {
      current = node - (*it);
      S[big].erase(current);
      if (S[big].size() < ss) {
        ans++;
        S[big].insert(current);
      }
    }
    for (it = S[small].begin(); it != S[small].end(); ++it) {
      current = (*it);
      S[big].insert(current);
    }
    S[small].clear();
    set_index[node] = big;
    S[big].insert(node);
  }
}
int main() {
  int n, i, j;
  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    scanf("%d", &P[i]);
    pos[P[i]] = i;
  }
  build(1, 0, n - 1);
  cartesian_tree(0, n - 1, n);
  dfs(n);
  printf("%I64d", ans);
  return 0;
}
