# Problem E

Eerie Subarrays

Brandon Greg Jr. considers an array to be scary if **its leftmost element is the median** of its
elements. Given an array with **distinct**
elements $[p_1, p_2, \ldots , p_
n]$, Brandon wants to count the number of scary
subarrays.

A subarray is some contiguous chunk of elements $[p_ l, p_{l+1}, \ldots , p_ r]$ where $l\le r$. The median of a set of $n$ numbers is the middle number in sorted order if $n$ is odd, or the average of the middle two numbers in sorted order if $n$ is even. Note that all subarrays of length $1$ are scary, and no even-length subarrays are scary because the elements are all distinct.

## Input

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

The second line of input contains $n$ space-separated integers $p_ i$ ($1\le p_ i\le n$), representing the given array. It is guaranteed that the $p_ i$’s are distinct.

## Output

Output one integer representing the number of scary subarrays.

Sample Input 1 | Sample Output 1 |
---|---|

5 1 2 3 4 5 |
5 |

Sample Input 2 | Sample Output 2 |
---|---|

6 3 2 1 6 4 5 |
8 |

Sample Input 3 | Sample Output 3 |
---|---|

7 2 1 5 3 6 7 4 |
11 |