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

public class CF1156E {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] aa = new int[n + 1];
		int[] ii = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			int a = Integer.parseInt(st.nextToken());
			aa[i] = a;
			ii[a] = i;
		}
		int[] ll = new int[n + 1];
		int[] rr = new int[n + 1];
		for (int i = 1; i <= n; i++)
			ll[i] = rr[i] = i;
		boolean[] used = new boolean[n + 1];
		int cnt = 0;
		for (int a = 1; a <= n; a++) {
			int i = ii[a];
			int l = i - 1 >= 1 && used[i - 1] ? ll[i - 1] : i;
			int r = i + 1 <= n && used[i + 1] ? rr[i + 1] : i;
			rr[l] = r;
			ll[r] = l;
			if (i + i <= l + r)
				for (int h = l; h < i; h++) {
					int j = ii[a - aa[h]];
					if (i < j && j <= r)
						cnt++;
				}
			else
				for (int h = r; h > i; h--) {
					int j = ii[a - aa[h]];
					if (l <= j && j < i)
						cnt++;
				}
			used[i] = true;
		}
		System.out.println(cnt);
	}
}
