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;
int arr[200001];
int rAns[200001];
int lAns[200001];
int Pos[200001];
int main() {
  cin.sync_with_stdio(false);
  int n;
  stack<int> mystack;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    rAns[i] = n - 1;
    lAns[i] = 0;
  }
  for (int i = 0; i < n; ++i) {
    cin >> arr[i];
    Pos[arr[i]] = i;
  }
  for (int i = 0; i < n; ++i) {
    while (!mystack.empty() && arr[i] > arr[mystack.top()]) {
      int a = mystack.top();
      mystack.pop();
      rAns[a] = i - 1;
    }
    mystack.push(i);
  }
  for (int i = n - 1; i >= 0; --i) {
    while (!mystack.empty() && arr[i] > arr[mystack.top()]) {
      int a = mystack.top();
      mystack.pop();
      lAns[a] = i + 1;
    }
    mystack.push(i);
  }
  long long ret = 0;
  for (int i = 0; i < n; ++i) {
    if (lAns[i] < i && rAns[i] > i) {
      int l = i - lAns[i];
      int r = rAns[i] - i;
      if (l < r) {
        for (int j = lAns[i]; j < i; ++j) {
          int tar = arr[i] - arr[j];
          if (Pos[tar] > i && Pos[tar] <= rAns[i]) ++ret;
        }
      } else {
        for (int j = i + 1; j <= rAns[i]; ++j) {
          int tar = arr[i] - arr[j];
          if (Pos[tar] >= lAns[i] && Pos[tar] < i) ++ret;
        }
      }
    }
  }
  cout << ret;
}
