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>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;
const int maxn = 2e5 + 5;
const int iinf = 1 << 29;
const long long inf = 1ll << 60;
const long long mod = 1e9 + 7;
void GG() {
  cout << "-1\n";
  exit(0);
}
unordered_map<int, bool> val[maxn];
int par[maxn];
int rnk[maxn];
int N;
vector<int> a;
void setUp(int n) {
  for (int i = 0; i < (n); i++) par[i] = i;
  for (int i = 0; i < (n); i++) rnk[i] = 1;
  int in;
  for (int i = 0; i < (n); i++) val[i][a[i]] = 1;
}
int find(int x) {
  if (x == par[x]) return x;
  return par[x] = find(par[x]);
}
long long re = 0;
void Bmerge(int a, int b, int M) {
  if (rnk[find(a)] < rnk[find(b)]) swap(a, b);
  int B = find(b), A = find(a);
  for (pair<int, int> x : val[B]) {
    if (val[A].count(M - x.first)) re++;
  }
  for (pair<int, int> x : val[B]) {
    val[A][x.first] = 1;
  }
  rnk[A] += rnk[B];
  par[B] = A;
}
void merge(int a, int b) {
  if (rnk[find(a)] < rnk[find(b)]) swap(a, b);
  int B = find(b), A = find(a);
  for (pair<int, int> x : val[B]) {
    val[A][x.first] = 1;
  }
  rnk[A] += rnk[B];
  par[B] = A;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> N;
  vector<int> fnd(N);
  int in;
  for (int i = 0; i < (N); i++) cin >> in, a.push_back(in - 1), fnd[a[i]] = i;
  setUp(N);
  for (int i = 0; i < (N); i++) {
    int at = fnd[i];
    if (at and a[at - 1] < a[at] and at != N - 1 and a[at + 1] < a[at]) {
      Bmerge(at - 1, at + 1, a[at] - 1);
      merge(at - 1, at);
    } else {
      if (at and a[at - 1] < a[at])
        merge(at - 1, at);
      else if (at != N - 1 and a[at + 1] < a[at])
        merge(at + 1, at);
    }
  }
  cout << re << endl;
}
