I. d-parkour
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

After winning the programming marathon, you decide to seek a new challenge and start training for the ICPC (International Collegiate Parkour Contest). This competition will take place in Diomedes-land.

In Diomedes-land, there are $$$N$$$ buildings with positive heights $$$h_1, \ldots, h_N$$$, and 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), note that this sequence could be empty when the competitor pass only one building.

For a competition between buildings $$$(i, j)$$$ to be fair, the sequence of ascents and descents from $$$i$$$ to $$$j$$$ must be the same as 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, and from right to left, it is also UD (meaning the competitor going from $$$i$$$ to $$$j$$$ ascends if and only if the competitor going from $$$j$$$ to $$$i$$$ ascends). 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 (down twice), but from right to left, it is UU (up twice). Finally, if the buildings between $$$i$$$ and $$$j$$$ have heights $$$3, 4, 2, 1, 5$$$, the competition would not be fair because the sequence from left to right is UDDU, but from right to left, it is DUUD (note that even though they go up and down the same number of times, the sequence of ups and downs is not the same).

To prepare for the competition, you want to know how many pairs $$$(i, j)$$$ with $$$i \leq j$$$ result in a fair competition (you have faith in the ICPC organization).

Input

The input consists of an integer $$$1 \leq N \leq 10^6$$$ representing the number of buildings in Diomedes-land, followed by $$$N$$$ integers representing the heights of the buildings $$$h_1, \ldots, h_N$$$ $$$(1 \leq h_i \leq 10^9$$$ for all $$$1\le i \le N)$$$.

Output

Print the number of pairs $$$(i, j)$$$ such that the competition between buildings from $$$i$$$ to $$$j$$$ is a fair competition.

Example
Input
5
2 5 7 1 3
Output
7