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 inf = 1000000000;
long long mod = 1000000007LL;
long long mod2 = 998244353LL;
int n;
int p[200005];
int pmax[200005][20];
int pos[200005];
long long ans;
void dfs(int l, int r) {
  if (l >= r) return;
  int pw = 0;
  while ((1 << pw) <= (r - l + 1)) {
    pw++;
  }
  pw--;
  int id1 = pmax[l][pw];
  int id2 = pmax[r - (1 << pw) + 1][pw];
  int id = -1;
  if (id2 < 0 || (id1 >= 0 && p[id1] > p[id2])) {
    id = id1;
  } else {
    id = id2;
  }
  if (id - l < r - id) {
    for (int i = l; i < id; ++i) {
      if (pos[p[id] - p[i]] > id && pos[p[id] - p[i]] <= r) {
        ans++;
      }
    }
  } else {
    for (int i = id + 1; i <= r; ++i) {
      if (pos[p[id] - p[i]] < id && pos[p[id] - p[i]] >= l) {
        ans++;
      }
    }
  }
  dfs(l, id - 1);
  dfs(id + 1, r);
}
int main() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &p[i]);
    pos[p[i]] = i;
  }
  memset(pmax, -1, sizeof(pmax));
  for (int i = 1; i <= n; ++i) {
    pmax[i][0] = i;
  }
  for (int i = 1; (1 << i) <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      if (j + (1 << i) - 1 <= n) {
        if (pmax[j][i - 1] >= 0 &&
            (pmax[j][i] < 0 || p[pmax[j][i]] < p[pmax[j][i - 1]])) {
          pmax[j][i] = pmax[j][i - 1];
        }
        if (pmax[j + (1 << (i - 1))][i - 1] >= 0 &&
            (pmax[j][i] < 0 ||
             p[pmax[j][i]] < p[pmax[j + (1 << (i - 1))][i - 1]])) {
          pmax[j][i] = pmax[j + (1 << (i - 1))][i - 1];
        }
      }
    }
  }
  ans = 0LL;
  dfs(1, n);
  cout << ans << endl;
  return 0;
}
