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 in() {
  int x;
  scanf("%d", &x);
  return x;
}
long long lin() {
  long long x;
  scanf("%lld", &x);
  return x;
}
long long MOD = 1e9 + 7;
template <typename Monoid>
struct SegmentTree {
  using F = function<Monoid(Monoid, Monoid)>;
  int sz;
  vector<Monoid> seg;
  const F f;
  const Monoid M1;
  SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) {
    sz = 1;
    while (sz < n) sz <<= 1;
    seg.assign(2 * sz, M1);
  }
  void set(int k, const Monoid &x) { seg[k + sz] = x; }
  void build() {
    for (int k = sz - 1; k > 0; k--) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }
  void update(int k, const Monoid &x) {
    k += sz;
    seg[k] = x;
    while (k >>= 1) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }
  Monoid query(int a, int b) {
    Monoid L = M1, R = M1;
    for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
      if (a & 1) L = f(L, seg[a++]);
      if (b & 1) R = f(seg[--b], R);
    }
    return f(L, R);
  }
  Monoid operator[](const int &k) const { return seg[k + sz]; }
};
int n;
int p[310000], pos[310000];
int main() {
  n = in();
  SegmentTree<int> seg(
      n + 1, [](int a, int b) { return a + b; }, 0);
  for (long long i = 0; i < n; i++) {
    p[i] = in();
    pos[p[i]] = i;
  }
  long long ans = 0;
  for (long long i = n; i >= 1; i--) {
    int s = pos[i];
    bool f;
    for (long long j = 0; j < n; j++) {
      if (s - j < 0 || p[s - j] > i) {
        f = true;
        break;
      }
      if (s + j >= n || p[s + j] > i) {
        f = false;
        break;
      }
    }
    if (f) {
      int t = s - 1;
      while (t >= 0 && p[t] < i) {
        if (pos[i - p[t]] > s && !seg.query(s, pos[i - p[t]] + 1)) ans++;
        t--;
      }
    } else {
      int t = s + 1;
      while (t < n && p[t] < i) {
        if (pos[i - p[t]] < s && !seg.query(pos[i - p[t]], s)) ans++;
        t++;
      }
    }
    seg.update(s, 1);
  }
  cout << ans;
}
