K. Entrance Exam
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You see the following problem in the TC University entrance exam:

Given an array $$$a$$$ of $$$n$$$ integers $$$a_1,a_2,...,a_n$$$, find the number of pairs of indices $$$(l,r)$$$ such that $$$1\le l\le r\le n$$$ and $$$$$$\max_{l\le i\le r} a_i+\min_{l\le i\le r} a_i=a_l+a_r.$$$$$$

Please solve it.

Input

The first line consists of an integer, $$$n$$$ ($$$1\le n\le 5\times 10^5$$$).

The second line consists of $$$n$$$ integers, $$$a_1,a_2,\dots,a_n$$$ ($$$1\le a_i\le 10^9$$$).

—

Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Test $$$1$$$ satisfies $$$n=1000$$$.

Tests $$$2-6$$$ satisfy $$$n\le 5\times 10^4$$$.

Tests $$$7-12$$$ satisfy $$$n\le 1\times 10^5$$$.

Tests $$$13-20$$$ satisfy no additional constraints.

Output

Output an integer, the number of pairs of indices $$$(l,r)$$$ such that $$$1\le l\le r\le n$$$ and $$$$$$\max_{l\le i\le r} a_i+\min_{l\le i\le r} a_i=a_l+a_r.$$$$$$

Example
Input
8
1 4 2 2 5 3 1 7
Output
21
Note

All such pairs $$$(l,r)$$$ are $$$$$$(1,1),(1,2),(1,5),(1,8),(2,2),$$$$$$ $$$$$$(2,3),(2,4),(2,6),(3,3),(3,4),$$$$$$ $$$$$$(3,5),(4,4),(4,5),(5,5),(5,6),$$$$$$ $$$$$$(5,7),(6,6),(6,7),(7,7),(7,8),(8,8).$$$$$$

—

Problem Idea: culver0412

Problem Preparation: culver0412

Occurrences: Advanced K