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 Maxn = 200005;
int n;
int P[Maxn];
int in[Maxn];
vector<int> seq[Maxn];
int par[Maxn];
long long res;
void unionSet(int a, int b, int wh) {
  a = par[a], b = par[b];
  if (a == b) return;
  if (seq[a].size() < seq[b].size()) swap(a, b);
  for (int i = 0; i < seq[b].size(); i++) {
    int my = P[seq[b][i]];
    res += my < wh && par[in[wh - my]] == a;
    seq[a].push_back(seq[b][i]);
  }
  for (int i = 0; i < seq[b].size(); i++) par[seq[b][i]] = a;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &P[i]);
    in[P[i]] = i;
    seq[i].push_back(i);
    par[i] = i;
  }
  for (int i = 1; i <= n; i++) {
    if (in[i] > 1 && P[in[i] - 1] < i) {
      seq[par[in[i] - 1]].push_back(in[i]);
      par[in[i]] = par[in[i] - 1];
    }
    if (in[i] < n && P[in[i] + 1] < i) unionSet(in[i], in[i] + 1, i);
  }
  cout << res << endl;
  return 0;
}
