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].
/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
If I'm the sun, you're the moon
Because when I go up, you go down
*******************************
I'm working for the day I will surpass you
https://www.a2oj.com/Ladder16.html
*/
import java.util.*;
import java.io.*;
import java.math.*;

   public class x1156E
   {
      public static void main(String omkar[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));  
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int N = Integer.parseInt(st.nextToken());
         int[] arr = new int[N];
         st = new StringTokenizer(infile.readLine());
         for(int i=0; i < N; i++)
            arr[i] = Integer.parseInt(st.nextToken());
         int[] loc = new int[N+1];
         for(int i=0; i < N; i++)
            loc[arr[i]] = i;
         int[] left = new int[N+1];
         int[] right = new int[N+1];
         Stack<Integer> stack = new Stack<Integer>();
         for(int i=0; i < N; i++)
         {
            while(stack.size() > 0 && stack.peek() < arr[i])
               right[stack.pop()] = i-1;
            stack.push(arr[i]);
         }
         while(stack.size() > 0) right[stack.pop()] = N-1;
         for(int i=N-1; i >= 0; i--)
         {
            while(stack.size() > 0 && stack.peek() < arr[i])
               left[stack.pop()] = i+1;
            stack.push(arr[i]);
         }
         int res = 0;
         for(int v=N; v >= 1; v--)
         {
            int mid = loc[v];
            if(mid-left[v] <= right[v]-mid)
            {
               for(int i=left[v]; i < mid; i++)
                  if(loc[v-arr[i]] > mid && loc[v-arr[i]] <= right[v])
                     res++;
            }
            else
            {
               for(int i=mid+1; i <= right[v]; i++)
                  if(loc[v-arr[i]] < mid && loc[v-arr[i]] >= left[v])
                     res++;
            }
         }
         System.out.println(res);
      }
   }