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>
#pragma GCC optimize("Ofast")
using namespace std;
const long long Mod = 1000000007LL, INF = 1e9, LINF = 1e18;
const long double Pi = 3.141592653589793116L;
const long double EPS = 0.000000001L, Gold = ((1.0L + sqrt(5.0L)) / 2.0L);
long long keymod[] = {1000000007LL, 1000000009LL, 1000000021LL, 1000000033LL};
mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
int OImode = 0;
int MultiTest = 0;
int Interactive = 0;
void ConfigMonitor();
char infile[] = "FILE.IN";
char outfile[] = "FILE.OUT";
int n;
vector<int> p, pos;
vector<vector<int>> Table;
void ProcessTable() {
  Table.resize(n);
  for (int j = 0; j < 20; j++) {
    for (int i = 0; i < n; i++) {
      if (i + (1 << j) > n) continue;
      if (j == 0) {
        Table[i].push_back(i);
        continue;
      }
      int id1 = Table[i][j - 1];
      int id2 = Table[i + (1 << (j - 1))][j - 1];
      if (p[id1] > p[id2])
        Table[i].push_back(id1);
      else
        Table[i].push_back(id2);
    }
  }
}
int maxarg(int L, int R) {
  int id = log2(R - L + 1);
  int p1 = Table[L][id];
  int p2 = Table[R + 1 - (1 << id)][id];
  if (p[p1] > p[p2]) return p1;
  return p2;
}
long long count(int L, int R) {
  if (L > R) return 0LL;
  int MA = maxarg(L, R);
  int Max = p[MA];
  long long res = count(L, MA - 1) + count(MA + 1, R);
  int x = L, y = MA - 1;
  if ((MA - L) > (R - MA)) {
    x = MA + 1;
    y = R;
  }
  for (int id = x; id <= y; id++) {
    int posreq = pos[Max - p[id]];
    res += (L <= posreq && posreq <= R && !(x <= posreq && posreq <= y));
  }
  return res;
}
void Input() {
  cin >> n;
  p.resize(n);
  pos.resize(n + 1);
  for (int i = 0; i < n; i++) {
    cin >> p[i];
    pos[p[i]] = i;
  }
}
void Solve() {
  ProcessTable();
  cout << count(0, n - 1) << '\n';
}
int main(int argc, char* argv[]) {
  ConfigMonitor();
  ios_base::sync_with_stdio(false);
  if (!Interactive) cin.tie(NULL);
  int T = 1;
  if (MultiTest) cin >> T;
  while (T--) {
    Input();
    Solve();
  }
  return 0;
}
void ConfigMonitor() {
  if (OImode) {
    freopen(infile, "r", stdin);
    freopen(outfile, "w", stdout);
  }
}
