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 int maxn = 2e5 + 5;
int arr[maxn], seg[maxn * 4], pos[maxn];
void build(int l, int r, int node) {
  if (l == r) {
    cin >> arr[l];
    seg[node] = arr[l];
    pos[arr[l]] = l;
  } else {
    int m = (l + r) >> 1;
    build(l, m, node * 2);
    build(m + 1, r, node * 2 + 1);
    seg[node] = max(seg[node * 2], seg[node * 2 + 1]);
  }
}
int query(int a, int b, int l, int r, int node) {
  if (a <= l && r <= b)
    return seg[node];
  else {
    int m = (l + r) >> 1, ret = 0;
    if (a <= m) ret = max(ret, query(a, b, l, m, node * 2));
    if (b > m) ret = max(ret, query(a, b, m + 1, r, node * 2 + 1));
    return ret;
  }
}
int main() {
  int n, ans = 0;
  cin >> n;
  build(1, n, 1);
  arr[0] = (1 << 30);
  arr[n + 1] = (1 << 30);
  for (int i = 1; i <= n; i++) {
    int j = 1;
    set<int> st;
    while (1) {
      if (arr[i - j] > arr[i] || arr[i + j] > arr[i]) break;
      int x1 = arr[i] - arr[i - j], x2 = arr[i] - arr[i + j];
      int site1 = pos[x1], site2 = pos[x2];
      if (site1 > i - j && st.count(i - j) == 0 && st.count(site1) == 0) {
        if (query(i - j, site1, 1, n, 1) == arr[i])
          ans++, st.insert(i - j), st.insert(site1);
      }
      if (site2 < i + j && st.count(i + j) == 0 && st.count(site2) == 0) {
        if (query(site2, i + j, 1, n, 1) == arr[i])
          ans++, st.insert(i + j), st.insert(site2);
      }
      j++;
    }
  }
  cout << ans;
  return 0;
}
