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.*;
public class Main{
	public static int getSegmentPairs(int[] nums) {
		int result = 0, len = nums.length;
		Stack<Integer> stack = new Stack<>();
		stack.push(-1);
		int[] index = new int[len + 1];
		for (int i = 0; i < len; i++) index[nums[i]] = i;
		for (int i = 0; i < len; i++) {
			while (stack.peek() != -1 && nums[i] > nums[stack.peek()]) {
				int x = stack.pop();
				if (x - stack.peek() < i - x) {
					for (int j = stack.peek() + 1; j < x; j++) {
						if (index[nums[x] - nums[j]] > x && index[nums[x] - nums[j]] < i) result++;
					}
				} else {
					for (int j = x + 1; j < i; j++) {
						if (index[nums[x] - nums[j]] > stack.peek() && index[nums[x] - nums[j]] < x) result++;
					}
				}
			}
			stack.push(i);
		}
		while (stack.peek() != -1) {
			int x = stack.pop();
			if (x - stack.peek() < len - x) {
				for (int i = stack.peek() + 1; i < x; i++) {
					if (index[nums[x] - nums[i]] > x && index[nums[x] - nums[i]] < len) result++;
				}
			} else {
				for (int i = x + 1; i < len; i++) {
					if (index[nums[x] - nums[i]] > stack.peek() && index[nums[x] - nums[i]] < x) result++;
				}
			}
		}
		return result;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int len = sc.nextInt();
		int[] nums = new int[len];
		for (int i = 0; i < len; i++) {
			nums[i] = sc.nextInt();
		}
		System.out.println(getSegmentPairs(nums));
	}
}