Large Weird Measurements

Interview

Time limit2sMemory limit512 MB

Summary

Count all contiguous intervals whose consecutive differences strictly alternate in sign, with any length-1 interval counting as weird.

Level: Medium5 of 10
Topics: Array, Two pointers, Implementation, Math
Solved: No attempts yet

Problem

"Almonds? Oh yeah, I have tried those before. Covered in chocolate." Dudu, 2015.

Dudu is getting in shape for a trip to Thailand, so he weighs himself every morning.

Some stretches of days are good, with the weight going down day after day. Some are bad, with the weight going up day after day. Others are just weird.

An interval of measurements is weird if it alternates between going up and going down. For example, if the measurements on consecutive days are 1, 3, 2, 5, 1, that interval is weird. The measurements 1, 3, 5, 4 are not weird, because the value goes up from 1 to 3 and then up again from 3 to 5. Two neighbouring measurements that are equal go neither up nor down, so an interval holding two equal neighbours is not weird unless its length is 1. Every interval of length 1 is weird.

Given the sequence of measurements, count the weird intervals. Two intervals at different positions count separately even when they hold the same values.

Input

The first line contains the length $N$ of the sequence.

The second line contains the measurements $a_1, a_2, \dots, a_N$ in day order.

$1 \le N \le 200\,000$
$0 \le a_i \le 10^9$

Output

Print one integer, the number of non-empty intervals of the sequence whose measurements are weird.

Hint

For the sequence 1 4 4 2 5 2 1 the weird intervals are [1], [1,4], [4], [4], [4,2], [4,2,5], [4,2,5,2], [2], [2,5], [2,5,2], [5], [5,2], [2], [2,1], [1].

There are two intervals at different positions that hold only the value 4, so 4 alone is counted twice.

Examples2

Example 1
Input
```
7
1 4 4 2 5 2 1
```
Expected output
```
15
```
Example 2
Input
```
5
1 3 2 5 1
```
Expected output
```
15
```