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.*;

public class Main {
	public static void main(String args[]) { new Main().WORK(); }
	
	Scanner in = new Scanner(System.in);
	PrintWriter out = new PrintWriter(System.out);
	
	final int N = (int)(2e5+10);
	
	int[] p = new int[N];
	HashSet<Integer>[] S = new HashSet[N];
	
	int find(int x) {
		if(x == p[x]) return x;
		p[x] = find(p[x]);
		return p[x];
	}
	
	void merge(int x, int y) {
		x = find(x); y = find(y);
		if(x == y) return;
		if(S[x].size() > S[y].size()) {
			int t = x; x = y; y = t;
		}
		S[y].addAll(S[x]);
		S[x].clear();
		p[x] = y;
	}
	
	int query(int x, int y, int mx) {
		int ret = 0;
		x = find(x); y = find(y);
		if(S[x].size() > S[y].size()) {
			int t = x; x = y; y = t;
		}
		for(int t:S[x]) {
			if(S[y].contains(mx-t)) ret++;
		}
		return ret;
	}
	
	void WORK() {
		int n = in.nextInt();
		boolean[] vis = new boolean[n+5];
		int[] a = new int[n+1], pos = new int[n+5];
		for(int i = 1; i <= n; i++) {
			a[i] = in.nextInt();
			pos[a[i]] = i;
			p[i] = i;
			S[i] = new HashSet<>();
			S[i].add(a[i]);
		}
		long ans = 0;
		for(int i = 1; i <= n; i++) {
			if(vis[pos[i]-1] && vis[pos[i]+1])
				ans += query(pos[i]-1, pos[i]+1, i);
			if(vis[pos[i]-1]) merge(pos[i]-1, pos[i]);
			if(vis[pos[i]+1]) merge(pos[i]+1, pos[i]);
			vis[pos[i]] = true;
		}
		out.println(ans);
		out.flush();
	}
}