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 tree[530000];
int get(int x, int l, int r, int L, int R) {
  if (r < L || R < l) return 0;
  if (L <= l && r <= R) return tree[x];
  int m = (l + r) >> 1;
  int nx = (x << 1);
  return max(get(nx, l, m, L, R), get(nx + 1, m + 1, r, L, R));
}
void push(int x, int l, int r, int pos, int val) {
  if (r < pos || pos < l) return;
  if (l == r) {
    tree[x] = val;
    return;
  }
  int m = (l + r) >> 1;
  int nx = (x << 1);
  push(nx, l, m, pos, val);
  push(nx + 1, m + 1, r, pos, val);
  tree[x] = max(tree[nx], tree[nx + 1]);
}
int N, arr[200001], p[200001], answ;
void f(int l, int r) {
  if (l >= r) return;
  int MAX = get(1, 1, N, l, r);
  int w = p[MAX], m = (l + r) >> 1;
  if (w <= m) {
    for (int i = l; i < w; i++) {
      int j = p[MAX - arr[i]];
      if (w < j && j <= r) answ++;
    }
  } else {
    for (int i = r; i > w; i--) {
      int j = p[MAX - arr[i]];
      if (l <= j && j < w) answ++;
    }
  }
  f(l, w - 1), f(w + 1, r);
}
int main() {
  scanf("%d", &N);
  for (int i = 1; i <= N; i++) {
    scanf("%d", &arr[i]);
    p[arr[i]] = i;
    push(1, 1, N, i, arr[i]);
  }
  f(1, N);
  printf("%d", answ);
}
