After losing the ICPC (International Collegiate Parkour Contest), you decided to participate in a parkour competition with different rules. You have traveled to Silvestre-land, where a new parkour competition will take place.
Similar to Diomedes-land, in Silvestre-land, there are $$$N$$$ buildings with positive heights $$$h_1, \ldots, h_N$$$, it is guaranteed that all building heights are distinct.
Each round of the competition will face two competitors, and it will take place from building $$$i$$$ to building $$$j$$$, where $$$i \leq j$$$. One competitor will jump between buildings from $$$i$$$ to $$$j$$$, while the other will jump from $$$j$$$ to $$$i$$$.
When a competitor jumps between buildings, they may have to ascend or descend. If the height of the next building is greater than the current one, they must ascend; otherwise, they must descend. For example, if the competitor passes through buildings with heights $$$1, 7, 2$$$, they first ascend and then descend, which we can represent with the sequence UD (Up, Down).
For a competition between buildings $$$(i, j)$$$ to be fair, the number of ascents from $$$i$$$ to $$$j$$$ must be equal to the number of ascents from $$$j$$$ to $$$i$$$. For example, if the buildings between $$$i$$$ and $$$j$$$ have heights $$$1, 7, 2$$$, the competition is fair because, from left to right, the sequence of ascents and descents is UD (one ascent and one descent), and from right to left, it is also UD (one ascent and one descent). However, if the buildings between $$$i$$$ and $$$j$$$ have heights $$$3, 2, 1$$$, the competition would not be fair because the sequence from left to right is DD (no ascents and two descents), but from right to left, it is UU (two ascents and no descents). Finally, if the buildings between $$$i$$$ and $$$j$$$ have heights $$$3, 4, 2, 1, 5$$$, the competition would be fair because the sequence from left to right is UDDU (two ascents and two descents), and from right to left, it is DUUD (two ascents and two descents).
To prepare for the competition, you want to know how many pairs $$$(i, j)$$$ with $$$i \leq j$$$ result in a fair competition.
The input consists of an integer $$$1 \leq N \leq 10^6$$$ representing the number of buildings in Silvestre-land, followed by $$$N$$$ integers representing the heights of the buildings $$$h_1, \ldots, h_N$$$.
$$$1 \leq h_i \leq 10^9$$$ for every $$$i$$$.
Print the number of pairs $$$(i, j)$$$ such that the competition between buildings from $$$i$$$ to $$$j$$$ is a fair competition.
66 1 4 9 7 3
10
