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;
void SolveA() {
  size_t n;
  size_t res = 0;
  const size_t m[3][3] = {{0, 3, 4}, {3, 0, 0}, {4, 0, 0}};
  cin >> n;
  vector<size_t> v(n);
  for (size_t i = 0; i < n; ++i) {
    cin >> v[i];
    --v[i];
  }
  for (size_t i = 1; i < n; ++i) {
    if (m[v[i - 1]][v[i]] == 0) {
      cout << "Infinite";
      return;
    }
    res += m[v[i - 1]][v[i]];
    if (i > 1 && v[i] == 1 && v[i - 2] == 2) --res;
  }
  cout << "Finite\n" << res;
}
void SolveB() {
  size_t T;
  {
    string tmp;
    getline(cin, tmp);
    stringstream ss(tmp);
    ss >> T;
  }
  for (int iTest = 0; iTest < T; ++iTest) {
    string s;
    getline(cin, s);
    size_t cnt[26] = {0};
    for (size_t i = 0; i < s.length(); ++i) ++cnt[s[i] - 'a'];
    size_t n[2] = {0};
    for (size_t i = 0; i < 26; ++i) n[i % 2] += cnt[i];
    if (n[0] * n[1] == 0) {
      for (size_t i = 0; i < 26; ++i)
        for (size_t j = 0; j < cnt[i]; ++j) cout << char('a' + i);
      cout << "\n";
      continue;
    }
    string tr(2, ' ');
    for (size_t i = 0; i < 26 && tr[0] == ' '; ++i)
      for (size_t j = 0; j < 26 && tr[0] == ' '; ++j) {
        if ((i % 2) != 0 || (j % 2) != 1) continue;
        if (cnt[i] == 0 || cnt[j] == 0) continue;
        if (i <= j + 1 && j <= i + 1) continue;
        tr[0] = 'a' + i;
        tr[1] = 'a' + j;
        --cnt[i];
        --cnt[j];
      }
    if (tr[0] == ' ') {
      cout << "No answer\n";
    } else {
      for (size_t i = 0; i < 26; i += 2)
        for (size_t j = 0; j < cnt[i]; ++j) cout << char('a' + i);
      cout << tr;
      for (size_t i = 1; i < 26; i += 2)
        for (size_t j = 0; j < cnt[i]; ++j) cout << char('a' + i);
      cout << "\n";
    }
  }
}
void SolveC() {
  cin.sync_with_stdio(false);
  cout.sync_with_stdio(false);
  size_t n, z;
  cin >> n >> z;
  vector<size_t> v(n);
  for (size_t i = 0; i < n; ++i) cin >> v[i];
  make_heap(v.begin(), v.end());
  sort_heap(v.begin(), v.end());
  size_t b = 0, e = n / 2;
  while (b < e) {
    size_t m = (b + e + 1) / 2;
    bool ok = true;
    for (size_t i = 0; i < m; ++i) {
      size_t dist = v[n - m + i] - v[i];
      ok = ok && (dist >= z);
    }
    if (ok)
      b = m;
    else
      e = m - 1;
  }
  cout << b;
}
void RecurseD(size_t n, size_t iCur, size_t iParent, const vector<size_t>& cnt,
              const vector<size_t>& pos, const vector<size_t>& iNeib,
              const vector<size_t>& cNeib, vector<long long>& n0,
              vector<long long>& n1, vector<long long>& n10,
              vector<long long>& n01, long long& res) {
  for (size_t i = 0; i < cnt[iCur]; ++i) {
    size_t iChild = iNeib[pos[iCur] + i];
    if (iChild == iParent) continue;
    RecurseD(n, iChild, iCur, cnt, pos, iNeib, cNeib, n0, n1, n10, n01, res);
    if (cNeib[pos[iCur] + i] == 0) {
      res += 2 * (1 + n0[iChild]);
      res += (n1[iChild] + n01[iChild]);
      n0[iCur] += (1 + n0[iChild]);
      n01[iCur] += (n1[iChild] + n01[iChild]);
    } else {
      res += 2 * (1 + n1[iChild]);
      res += (n0[iChild] + n10[iChild]);
      n1[iCur] += (1 + n1[iChild]);
      n10[iCur] += (n0[iChild] + n10[iChild]);
    }
  }
  res += (n0[iCur] * n0[iCur] + n1[iCur] * n1[iCur] + n0[iCur] * n1[iCur] +
          n01[iCur] * n0[iCur] + n10[iCur] * n1[iCur]);
  for (size_t i = 0; i < cnt[iCur]; ++i) {
    size_t iChild = iNeib[pos[iCur] + i];
    if (iChild == iParent) continue;
    if (cNeib[pos[iCur] + i] == 0) {
      res -= (n0[iChild] + 1) * (n0[iChild] + 1);
      res -= (n0[iChild] + 1) * (n1[iChild] + n01[iChild]);
    } else {
      res -= (n1[iChild] + 1) * (n1[iChild] + 1);
      res -= (n1[iChild] + 1) * (n0[iChild] + n10[iChild]);
    }
  }
}
void SolveD() {
  cin.sync_with_stdio(false);
  cout.sync_with_stdio(false);
  size_t n;
  cin >> n;
  vector<size_t> i1(n - 1), i2(n - 1), c(n - 1), cnt(n);
  for (size_t i = 0; i + 1 < n; ++i) {
    cin >> i1[i] >> i2[i] >> c[i];
    --i1[i];
    --i2[i];
    ++cnt[i1[i]];
    ++cnt[i2[i]];
  }
  vector<size_t> pos(n, 0);
  for (size_t i = 1; i < n; ++i) pos[i] = pos[i - 1] + cnt[i - 1];
  vector<size_t> iNeib(2 * n - 2);
  vector<size_t> cNeib(2 * n - 2);
  cnt.assign(n, 0);
  for (size_t i = 0; i + 1 < n; ++i) {
    size_t j = i1[i];
    size_t k = i2[i];
    iNeib[pos[j] + cnt[j]] = k;
    cNeib[pos[j] + cnt[j]] = c[i];
    ++cnt[j];
    iNeib[pos[k] + cnt[k]] = j;
    cNeib[pos[k] + cnt[k]] = c[i];
    ++cnt[k];
  }
  vector<long long> n0(n, 0), n1(n, 0), n10(n, 0), n01(n, 0);
  long long res = 0;
  RecurseD(n, 0, 0, cnt, pos, iNeib, cNeib, n0, n1, n10, n01, res);
  cout << res;
}
void SolveE() {
  cin.sync_with_stdio(false);
  cout.sync_with_stdio(false);
  size_t n;
  cin >> n;
  vector<size_t> v(n);
  for (size_t i = 0; i < n; ++i) {
    cin >> v[i];
    --v[i];
  }
  vector<size_t> pos(n);
  for (size_t i = 0; i < n; ++i) pos[v[i]] = i;
  vector<size_t> lp(n), rp(n);
  vector<size_t> stack;
  for (size_t i = 0; i < n; ++i) {
    while (!stack.empty() && v[stack.back()] < v[i]) stack.pop_back();
    if (stack.empty())
      lp[i] = 0;
    else
      lp[i] = stack.back() + 1;
    stack.push_back(i);
  }
  stack.clear();
  for (int i = n - 1; i >= 0; --i) {
    while (!stack.empty() && v[stack.back()] < v[i]) stack.pop_back();
    if (stack.empty())
      rp[i] = n - 1;
    else
      rp[i] = stack.back() - 1;
    stack.push_back(i);
  }
  size_t res = 0;
  for (size_t i = 0; i < n; ++i) {
    if (i - lp[i] > rp[i] - i) {
      for (size_t j = i + 1; j <= rp[i]; ++j) {
        size_t needed = v[i] - v[j] - 1;
        if (pos[needed] >= lp[i] && pos[needed] < i) ++res;
      }
    } else {
      for (size_t j = lp[i]; j < i; ++j) {
        size_t needed = v[i] - v[j] - 1;
        if (pos[needed] > i && pos[needed] <= rp[i]) ++res;
      }
    }
  }
  cout << res;
}
int main() {
  SolveE();
  return 0;
}
