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 N = 1e6;
vector<long long int> v(N), pos(N);
int n;
int t[2 * N];
void build() {
  for (int i = n - 1; i > 0; --i) t[i] = max(t[i << 1], t[i << 1 | 1]);
}
void modify(int p, int value) {
  for (t[p += n] = value; p > 1; p >>= 1) t[p >> 1] = max(t[p], t[p ^ 1]);
}
int query(int l, int r) {
  int res = 0;
  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
    if (l & 1) res = max(res, t[l++]);
    if (r & 1) res = max(res, t[--r]);
  }
  return res;
}
int solve(int l, int r) {
  if (r - l + 1 < 3) return 0;
  int ans = 0;
  int ma = query(l, r + 1);
  int x = pos[ma];
  ans += solve(l, x - 1) + solve(x + 1, r);
  if (x - l <= r - x)
    for (long long int i = l; i <= x - 1; i++) {
      int a = v[i], b = ma - a;
      if (a < ma && b > 0) {
        int posa = pos[a], posb = pos[b];
        if ((posa >= l && posa <= x - 1 && posb >= x + 1 && posb <= r) ||
            (posb >= l && posb <= x - 1 && posa >= x + 1 && posa <= r))
          ans++;
      }
    }
  else
    for (long long int i = x + 1; i <= r; i++) {
      int a = v[i], b = ma - a;
      if (a < ma && b > 0) {
        int posa = pos[a], posb = pos[b];
        if ((posa >= l && posa <= x - 1 && posb >= x + 1 && posb <= r) ||
            (posb >= l && posb <= x - 1 && posa >= x + 1 && posa <= r))
          ans++;
      }
    }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  cin >> n;
  for (long long int i = 0; i <= n - 1; i++)
    cin >> v[i], t[n + i] = v[i], pos[v[i]] = i;
  build();
  cout << solve(0, n - 1);
}
