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;
long long n, a[200010], ans = 0, x[200010];
pair<long long, long long> arvore[800010];
void montar(long long no, long long ini, long long fim) {
  if (ini == fim) {
    arvore[no] = {a[ini], ini};
    return;
  }
  long long meio = (ini + fim) / 2;
  montar(2 * no, ini, meio);
  montar(2 * no + 1, meio + 1, fim);
  if (arvore[2 * no].first < arvore[2 * no + 1].first)
    arvore[no] = arvore[2 * no + 1];
  else
    arvore[no] = arvore[2 * no];
}
pair<long long, long long> qq(long long no, long long ini, long long fim,
                              long long l, long long r) {
  if (l <= ini and fim <= r) return arvore[no];
  if (r < ini or fim < l) return {-9123456789, 0};
  long long meio = (ini + fim) / 2;
  pair<long long, long long> esq = qq(2 * no, ini, meio, l, r),
                             dir = qq(2 * no + 1, meio + 1, fim, l, r);
  if (esq.first < dir.first)
    return dir;
  else
    return esq;
}
void op(long long l, long long r, long long maior, long long pos) {
  if (r - l < 1) return;
  pair<long long, long long> esq = qq(1, 1, n, l, pos - 1),
                             dir = qq(1, 1, n, pos + 1, r);
  if (pos - l < r - pos) {
    for (long long i = l; i < pos; i++) {
      if (pos + 1 <= x[maior - a[i]] and x[maior - a[i]] <= r) {
        ans++;
      }
    }
  } else {
    for (long long i = pos + 1; i <= r; i++) {
      if (l <= x[maior - a[i]] and x[maior - a[i]] <= pos - 1) {
        ans++;
      }
    }
  }
  op(l, pos - 1, esq.first, esq.second);
  op(pos + 1, r, dir.first, dir.second);
}
void solve() {
  cin >> n;
  for (long long i = 1; i <= n; i++) cin >> a[i], x[a[i]] = i;
  montar(1, 1, n);
  op(1, n, n, x[n]);
  cout << ans;
}
signed main() { solve(); }
