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 arr[200005];
pair<int, int> tree[4 * 200005];
pair<int, int> combine(pair<int, int> a, pair<int, int> b) {
  if (a.first > b.first)
    return a;
  else
    return b;
}
void build(int node, int l, int r) {
  if (l == r)
    tree[node] = {arr[l], l};
  else {
    int mid = (l + r) / 2;
    build(node * 2, l, mid);
    build(node * 2 + 1, mid + 1, r);
    tree[node] = combine(tree[node * 2], tree[node * 2 + 1]);
  }
}
pair<int, int> sum(int node, int tl, int tr, int l, int r) {
  if (l > r) return {0, 0};
  if (l == tl && r == tr) return tree[node];
  int mid = (tl + tr) / 2;
  return combine(sum(node * 2, tl, mid, l, min(r, mid)),
                 sum(node * 2 + 1, mid + 1, tr, max(l, mid + 1), r));
}
int n;
int mp[200005];
int go(int lft, int rht) {
  if (rht - lft <= 1) return 0;
  pair<int, int> now = sum(1, 1, n, lft, rht);
  int val = now.first, pos = now.second;
  int ret = 0;
  if ((rht - pos) < (pos - lft)) {
    for (int i = pos + 1; i <= rht; i++) {
      int baki = val - arr[i];
      if (mp[baki] >= lft && mp[baki] < pos) ret++;
    }
  } else {
    for (int i = lft; i < pos; i++) {
      int baki = val - arr[i];
      if (mp[baki] <= rht && mp[baki] > pos) ret++;
    }
  }
  ret += go(lft, pos - 1) + go(pos + 1, rht);
  return ret;
}
int main() {
  int i, j;
  scanf("%d", &n);
  for (i = 1; i <= n; i++) {
    scanf("%d", &arr[i]);
    mp[arr[i]] = i;
  }
  build(1, 1, n);
  cout << go(1, n) << endl;
  return 0;
}
