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].
import java.util.*;
import java.io.*;

@SuppressWarnings("unchecked")
public class CF1156E {
	// why did I think I needed a segment tree?????
	class RMQ {
		int ind[][], max[][];
		public RMQ(int[] p) {
			int n = p.length;
			int lg = 32 - Integer.numberOfLeadingZeros(n);
			max = new int[lg][n];
			ind = new int[lg][n];
			for(int i = 0 ; i < n ; i++) {
				max[0][i] = p[i];
				ind[0][i] = i;
			}
			for(int k = 1, len = 1 ; k < lg ; k++, len <<= 1) {
				for(int i = 0 ; i < n ; i++) {
					if(max[k - 1][i] > max[k - 1][min(i + len, n - 1)]) {
						max[k][i] = max[k - 1][i];
						ind[k][i] = ind[k - 1][i];
					} else {
						max[k][i] = max[k - 1][min(i + len, n - 1)];
						ind[k][i] = ind[k - 1][min(i + len, n - 1)];
					}
				}
			}
		}
		int queryMax(int i, int j) {
			int exp = Integer.highestOneBit(j - i + 1);
			int k = Integer.numberOfTrailingZeros(exp);
			return max(max[k][i], max[k][j - exp + 1]);
		}
		int queryInd(int i, int j) {
			int exp = Integer.highestOneBit(j - i + 1);
			int k = Integer.numberOfTrailingZeros(exp);
			if(max[k][i] > max[k][j - exp + 1]) return ind[k][i];
			else return ind[k][j - exp + 1];
		}
	}
	long go(int l, int r) {
		if(r <= l) return 0;
		int max = rmq.queryMax(l, r);
		int ind = rmq.queryInd(l, r);
		long res = 0;
		if(abs(r - ind) < abs(l - ind)) {
			for(int i = ind + 1 ; i <= r ; i++)
				if(l <= rev[max - p[i]] && rev[max - p[i]] < ind)
					res++;
		} else {
			for(int i = l ; i < ind ; i++)
				if(ind < rev[max - p[i]] && rev[max - p[i]] <= r)
					res++;
		}
		return res + go(l, ind - 1) + go(ind + 1, r);
	}
	int[] p, rev;
	RMQ rmq;
	public CF1156E() {
		FS scan = new FS();
		int n = scan.nextInt();
		p = new int[n];
		rev = new int[n + 1];
		for(int i = 0 ; i < n ; i++) {
			p[i] = scan.nextInt();
			rev[p[i]] = i;
		}
		rmq = new RMQ(p);
		System.out.println(go(0, n - 1));
		// naive();
	}
	void naive() {
		int n = p.length;
		int res = 0;
		for(int i = 0 ; i < n ; i++) {
			for(int j = i ; j < n ; j++) {
				int max = 0;
				for(int k = i ; k <= j ; k++) {
					max = max(max, p[k]);
				}
				if(p[i] + p[j] == max) res++;
			}
		}
		System.out.println("real answer: " + res);
	}
	int abs(int x) { return max(x, -x); }
	int min(int a, int b) { return a < b ? a : b; }
	int max(int a, int b) { return a > b ? a : b; }
	class FS {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");
		public String next() {
			while(!st.hasMoreTokens()) {
				try { st = new StringTokenizer(br.readLine()); }
				catch(Exception e) { e.printStackTrace(); }
			}
			return st.nextToken();
		}
		public int nextInt() { return Integer.parseInt(next()); }
	}
	public static void main(String[] args) { new CF1156E(); }
}