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>
template <typename T>
inline void read(T &x) {
  x = 0;
  char c = getchar();
  bool flag = false;
  while (!isdigit(c)) {
    if (c == '-') flag = true;
    c = getchar();
  }
  while (isdigit(c)) {
    x = (x << 1) + (x << 3) + (c ^ 48);
    c = getchar();
  }
  if (flag) x = -x;
}
using namespace std;
int n;
int h[201000];
int stk[201000], stop;
int son[201000][2], fa[201000];
inline void build() {
  for (register int i = 1; i <= n; ++i) {
    while (stop && h[stk[stop]] < h[i]) son[i][0] = stk[stop], --stop;
    if (son[i][0]) fa[son[i][0]] = i;
    if (stop) son[stk[stop]][1] = i, fa[i] = stk[stop];
    stk[++stop] = i;
  }
}
int root;
inline void find_root() {
  for (register int i = 1; i <= n; ++i)
    if (!fa[i]) return root = i, void();
}
int hson[201000];
int siz[201000];
void dfs_son(int cur) {
  if (!cur) return;
  siz[cur] = 1;
  int mx = 0;
  for (register int i = 0; i <= 1; ++i) {
    int to = son[cur][i];
    dfs_son(to);
    siz[cur] += siz[to];
    if (siz[to] > mx) mx = siz[to], hson[cur] = i;
  }
}
long long ans;
int bin[201000];
void dfs_clear(int cur) {
  if (!cur) return;
  --bin[h[cur]];
  dfs_clear(son[cur][0]);
  dfs_clear(son[cur][1]);
}
void dfs_calc(int cur, int val) {
  if (!cur) return;
  ans += bin[val - h[cur]];
  dfs_calc(son[cur][0], val);
  dfs_calc(son[cur][1], val);
}
void dfs_add(int cur) {
  if (!cur) return;
  ++bin[h[cur]];
  dfs_add(son[cur][0]);
  dfs_add(son[cur][1]);
}
void dfs(int cur) {
  if (!cur) return;
  dfs(son[cur][hson[cur] ^ 1]);
  dfs_clear(son[cur][hson[cur] ^ 1]);
  dfs(son[cur][hson[cur]]);
  dfs_calc(son[cur][hson[cur] ^ 1], h[cur]);
  dfs_add(son[cur][hson[cur] ^ 1]);
  ++bin[h[cur]];
}
int main() {
  read(n);
  for (register int i = 1; i <= n; ++i) read(h[i]);
  build();
  find_root();
  dfs_son(root);
  dfs(root);
  printf("%lld\n", ans);
  return 0;
}
