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 namespace std::chrono;
template <typename A>
ostream &operator<<(ostream &cout, vector<A> const &v);
template <typename A, typename B>
ostream &operator<<(ostream &cout, pair<A, B> const &p) {
  return cout << "(" << p.first << ", " << p.second << ")";
}
template <typename A>
ostream &operator<<(ostream &cout, vector<A> const &v) {
  cout << "[";
  for (int i = 0; i < v.size(); i++) {
    if (i) cout << ", ";
    cout << v[i];
  }
  return cout << "]";
}
mt19937 rng(steady_clock::now().time_since_epoch().count());
void usaco(string filename) {
#pragma message("be careful, freopen may be wrong")
  freopen((filename + ".in").c_str(), "r", stdin);
  freopen((filename + ".out").c_str(), "w", stdout);
}
const long double pi = 3.14159265358979323846;
const long long mod = 1000000007;
long long n, m, k, q, Q, T, l, r, x, y, z;
long long a[1000005];
long long b[1000005];
long long c[1000005];
string second, t;
long long ans = 0;
map<int, int> vals[200005];
int mk[200005], sz[200005];
int main() {
  {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
  };
  cin >> n;
  for (long long i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (long long i = 0; i < n; i++) b[a[i]] = i;
  for (long long i = 0; i < n; i++) {
    mk[i] = i;
    sz[i] = 0;
  }
  for (long long j = 0; j < n; j++) {
    int i = b[j + 1];
    if (i == 0) {
      if (a[i] > a[i + 1]) {
        mk[i] = mk[i + 1];
      }
    } else if (i == n - 1) {
      if (a[i] > a[i - 1]) {
        mk[i] = mk[i - 1];
      }
    } else {
      if (a[i] < a[i - 1]) {
        if (a[i] > a[i + 1]) {
          mk[i] = mk[i + 1];
        }
      } else {
        if (a[i] < a[i + 1]) {
          mk[i] = mk[i - 1];
        } else {
          int small = i - 1, large = i + 1;
          if (sz[mk[small]] > sz[mk[large]]) swap(small, large);
          for (const pair<int, int> &x : vals[mk[small]]) {
            if (vals[mk[large]][a[i] - x.first])
              ++ans;
            else
              vals[mk[large]].erase(a[i] - x.first);
          }
          mk[i] = mk[large];
          int stor = mk[small];
          if (large == i - 1)
            for (long long k = i + 1; k < i + sz[stor] + 1; k++) {
              mk[k] = mk[large];
              ++vals[mk[large]][a[k]];
            }
          else
            for (long long k = i - sz[stor]; k < i; k++) {
              mk[k] = mk[large];
              ++vals[mk[large]][a[k]];
            }
          sz[mk[large]] += sz[stor];
        }
      }
    }
    ++vals[mk[i]][a[i]];
    ++sz[mk[i]];
  }
  cout << ans << endl;
}
