Counting Bitonic Subarrays

A sequence $[a_1, a_2, \dots, a_n]$ is called bitonic if there exists an index $m$ ($1 \leq m \leq n$) such that [ a_1 \leq a_2 \leq \dots \leq a_m \quad \text{and} \quad a_m \geq a_{m+1} \geq \dots \geq a_n. ] Note that a strictly increasing or strictly decreasing sequence is also considered bitonic.

Given a sequence, count the number of pairs $(l, r)$ with $1 \leq l \leq r \leq n$ such that the subarray $[a_l, a_{l+1}, \dots, a_r]$ is bitonic.

inputFormat

The first line contains an integer $n$, the length of the sequence. The second line contains $n$ space-separated integers $a_1, a_2, \dots, a_n$.

outputFormat

Output the number of pairs $(l, r)$ such that the subarray $[a_l, a_{l+1}, \dots, a_r]$ is bitonic.

sample

3
1 2 1

5