RCPC Simulare 2023 day 2 | K. Blabla

After hearing enough nonsense discussions, X decided to be concise 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 values in it 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 data

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

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

Output data

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

Example 1

stdin

7
1 2 3 1 1 3 2

stdout

17

Example 2

stdin

12
4 2 3 1 2 3 4 5 6 4 6 1

stdout

43