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 long long LINF = 0x3f3f3f3f3f3f3f3f;
const long long NLINF = 0xf7f7f7f7f7f7f7f7;
const int INF = 0x3f3f3f3f, NINF = 0xf7f7f7f7;
const int MOD1 = 1e9 + 7, MOD2 = 1e9 + 9;
const int N = 2e5 + 10;
int n, ans = 0, p[N], idx[N], l[N], r[N];
stack<int> s;
void check(int l, int r, int l_, int r_, int mx) {
  for (int i = l; i <= r; i++) {
    int v = mx - p[i];
    if (idx[v] <= r_ && idx[v] >= l_) ans++;
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &p[i]), idx[p[i]] = i;
  s.push(n + 1);
  for (int i = 1; i <= n; i++) {
    while (s.top() < p[i]) s.pop();
    l[i] = idx[s.top()] + 1;
    s.push(p[i]);
  }
  idx[n + 1] = n + 1, s.push(n + 1);
  for (int i = n; i > 0; i--) {
    while (s.top() < p[i]) s.pop();
    r[i] = idx[s.top()] - 1;
    s.push(p[i]);
  }
  for (int i = 1; i <= n; i++) {
    int lenl = i - l[i], lenr = r[i] - i;
    if (lenl < lenr)
      check(l[i], i - 1, i + 1, r[i], p[i]);
    else
      check(i + 1, r[i], l[i], i - 1, p[i]);
  }
  printf("%d\n", ans);
}
