Hide

# Problem EEerie 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

Hide