#89 Array and Counting 3

Statement

Statement language

A positive integer $N$ and a sequence $A = [A_1, A_2, \cdots, A_{N}]$ of length $N$ are given. Find the number of integer pairs $(l, r)$ that satisfy the following conditions.

$1 \leq l \leq r \leq N$ .
$\max(A_l, A_{l + 1}, \cdots, A_r) = A_l + A_r$ .

Input

The input is given in the following format.

$N$ $A_1 \ A_2 \ \cdots \ A_{N}$

Output

Print the answer on the first line.

Constraints

$1 \leq N \leq 200 \ 000$ .
$1 \leq A_i \leq 10^{18}$ ().

Subtasks

#	Score	Constraints
1	11	$N \leq 200$ .
2	27	$N \leq 2 \ 000$ .
3	62	No additional constraints.

Samples

Sample 1

Input

5
1 3 2 4 1

Output

2

Sample 2

Input

5
1 10 9 10 1

Output

2