Large Weird Measurements

"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.

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$

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

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.