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 ans;
int n;
int val[400008];
int where[400008];
set<int> ex;
set<int> onit[400008];
void merge(set<int> &a, set<int> &b) {
  for (set<int>::iterator it = b.begin(); it != b.end(); it++) a.insert(*it);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++)
    scanf("%d", &val[i]), where[val[i]] = i, ex.insert(i);
  ex.insert(0), ex.insert(n + 1), val[0] = val[n + 1] = n + 1;
  onit[where[1]].insert(1);
  for (int i = 2; i <= n; i++) {
    set<int> tol, tor;
    while (1) {
      int x = *(--ex.find(where[i]));
      if (val[x] > i) break;
      if (onit[x].size() > tol.size()) swap(tol, onit[x]);
      merge(tol, onit[x]);
      ex.erase(x);
    }
    while (1) {
      int x = *(++ex.find(where[i]));
      if (val[x] > i) break;
      if (onit[x].size() > tor.size()) swap(tor, onit[x]);
      merge(tor, onit[x]);
      ex.erase(x);
    }
    if (tol.size() > tor.size()) swap(tol, tor);
    for (set<int>::iterator it = tol.begin(); it != tol.end(); it++)
      if (tor.count(i - *it)) ans++;
    merge(tor, tol);
    swap(onit[where[i]], tor);
    onit[where[i]].insert(i);
  }
  printf("%lld\n", ans);
  return 0;
}
