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;
inline int read() {
  int s = 0, t = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') t = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    s = (s << 3) + (s << 1) + (ch ^ 48), ch = getchar();
  return s * t;
}
const int N = 2e5 + 5;
int n, a[N], mp[N], Lg[N], p[N][18];
long long Ans;
struct Node {
  int x, op;
};
vector<Node> G[N];
int Find(int l, int r) {
  int k = Lg[r - l + 1], x = p[l][k], y = p[r - (1 << k) + 1][k];
  return a[x] > a[y] ? x : y;
}
void Ins(int l, int r, int x) {
  G[l - 1].push_back((Node){x, -1});
  G[r].push_back((Node){x, +1});
}
void Solve(int l, int r) {
  if (l > r) return;
  int t = Find(l, r);
  if (t - l < r - t)
    for (int i = l; i <= t; i++) Ins(t, r, a[t] - a[i]);
  else
    for (int i = t; i <= r; i++) Ins(l, t, a[t] - a[i]);
  Solve(l, t - 1), Solve(t + 1, r);
}
int main() {
  n = read();
  for (int i = 1; i <= n; i++) a[i] = read(), p[i][0] = i;
  for (int i = 2; i <= n; i++) Lg[i] = Lg[i >> 1] + 1;
  for (int j = 1; j <= 17; j++)
    for (int i = 1; i + (1 << j) - 1 <= n; i++) {
      int x = p[i][j - 1], y = p[i + (1 << j - 1)][j - 1];
      p[i][j] = a[x] > a[y] ? x : y;
    }
  Solve(1, n);
  for (int i = 1; i <= n; i++) {
    mp[a[i]]++;
    for (auto t : G[i]) Ans += mp[t.x] * t.op;
  }
  printf("%lld", Ans);
  return 0;
}
