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;
using ull = unsigned long long;
using ll = long long;
const int N = 200005, LG = 19, MOD = 1e9 + 7;
int n, p[N], st[N][LG], sz[N], lg[N], cnt[N];
vector<int> g[N], vc[N];
void siz(int u, int p = -1) {
  sz[u] = 1;
  for (auto v : g[u]) {
    if (v != p) {
      siz(v, u);
      sz[u] += sz[v];
    }
  }
}
int dfs(int u, int p = -1, bool kp = 0) {
  int mx = 0, bg = -1, ans = 0;
  for (auto v : g[u]) {
    if (v != p && mx < sz[v]) {
      mx = sz[v];
      bg = v;
    }
  }
  for (auto v : g[u]) {
    if (v != p && v != bg) {
      ans += dfs(v, u);
    }
  }
  if (bg != -1) {
    ans += dfs(bg, u, 1);
    swap(vc[u], vc[bg]);
  }
  vc[u].push_back(u), ++cnt[u];
  for (auto v : g[u]) {
    if (v != p && v != bg) {
      for (auto x : vc[v]) {
        ans += cnt[u - x] != 0;
      }
      for (auto x : vc[v]) {
        ++cnt[x];
        vc[u].push_back(x);
      }
    }
  }
  if (!kp) {
    for (auto x : vc[u]) {
      --cnt[x];
    }
  }
  return ans;
}
int get(int l, int r) {
  int j = lg[r - l + 1];
  int ans = st[l][j];
  if (p[st[r - (1 << j) + 1][j]] > p[ans]) ans = st[r - (1 << j) + 1][j];
  return ans;
}
void add(int u, int v) { g[u].push_back(v), g[v].push_back(u); }
int build(int l, int r) {
  int j = get(l, r);
  if (l != j) {
    add(p[j], build(l, j - 1));
  }
  if (r != j) {
    add(p[j], build(j + 1, r));
  }
  return p[j];
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> p[i];
    st[i][0] = i;
  }
  for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
  for (int j = 1; j < LG; ++j) {
    for (int i = 0; i + (1 << j) <= n; ++i) {
      st[i][j] = st[i][j - 1];
      if (p[st[i + (1 << (j - 1))][j - 1]] > p[st[i][j]]) {
        st[i][j] = st[i + (1 << (j - 1))][j - 1];
      }
    }
  }
  build(0, n - 1);
  siz(n);
  cout << dfs(n) << '\n';
  return 0;
}
