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

After hearing enough nonsense discussions, X decided to be short with the next problem's statement.

Given an array of length $$$n$$$, find out how many subarrays exist such that the difference between the maximum and minimum value is at least equal to the difference between the first and the last position of the subarray.

More formally, if we have the subarray $$$[L, R]$$$, whose maximum value is $$$A$$$ and whose minimum value is $$$B$$$, we want $$$A - B \geq R - L$$$.

Input

The first line of the input contains $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$), the length of the array.

The next line of the input contains the array of length $$$n$$$, where $$$v_i$$$ ($$$1 \le v_i \le 2 \cdot 10^5$$$) is the $$$i_{th}$$$ value of the array.

Output

The output will contain a single integer, representing the number of subarrays found.

Examples
Input
7
1 2 3 1 1 3 2
Output
17
Input
12
4 2 3 1 2 3 4 5 6 4 6 1
Output
43