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

public class SpecialPer{
	public static int ans = 0;

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);

		int n = scan.nextInt();
		int[] array = new int[n+1];
		int[] num2Index = new int[n+1];
		for(int i=1;i<=n;i++){
			array[i] = scan.nextInt();
			num2Index[array[i]] = i;
		}

		int[] preHigher = new int[n+1];
		int[] postHigher = new int[n+1];
		Deque<Integer> deque = new ArrayDeque<>();
		for(int i=1;i<=n;i++){
			while(deque.size()!=0 && array[deque.peekLast()]<array[i]){
				deque.pollLast();
			}

			preHigher[i] = (deque.size()==0)?0:deque.peekLast();
			deque.offerLast(i);
		}
		while(deque.size()!=0){
			deque.pollLast();
		}

		for(int i=n;i>=1;i--){
            while(deque.size()!=0 && array[i]>array[deque.peekFirst()]){
            	deque.pollFirst();
            }

            postHigher[i] = deque.size()==0?(n+1):deque.peekFirst();
            deque.offerFirst(i);
		}


		for(int i=1;i<=n;i++){
			int pre_i = preHigher[i];
			int post_i = postHigher[i];
			int left_len = i-pre_i-1;
			int right_len = post_i - i - 1;

			if(left_len < right_len){
                checkSpecial(array, num2Index, array[i], pre_i+1, i-1, i+1, post_i-1);
			}else{
			    checkSpecial(array, num2Index, array[i], i+1, post_i-1, pre_i+1, i-1);
			}
		}



		System.out.println(ans);

	}


	public static void checkSpecial(int[] array, int[] num2Index, int sum, int left_i, int left_j, int right_i, int right_j){
            for(int index=left_i; index<=left_j; index++){
                   int o_val = sum - array[index];

                   int o_index = num2Index[o_val];
                   if(o_index>=right_i && o_index<=right_j){
                   	    ans++;
                   }    
            }
	}
}