Weird Measurements (Medium)

Interview

Time limit2sMemory limit512 MB

Summary

Count the contiguous subarrays whose consecutive differences alternate in sign, with no zero differences allowed.

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

Problem

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

Dudu is getting in shape for an upcoming trip to Thailand. As part of the plan he records his weight every morning.

Over some stretches of days the weight drops steadily, and over others it climbs steadily. Some stretches move strangely.

An interval of records is weird if it alternates between increasing and decreasing. For example, records of 1, 3, 2, 5, 1 on consecutive days are weird. Records of 1, 3, 5, 4 are not weird, because the value increases from 1 to 3 and then again from 3 to 5. Every interval of length 1 is weird.

If two neighbouring records are equal, that change is neither an increase nor a decrease, so an interval that contains both of them is not weird.

Given the sequence of records, count the weird intervals.

Input

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

The second line contains the $N$ integers $a_1, a_2, \dots, a_N$ of the sequence, separated by spaces.

$1 \le N \le 5000$
$0 \le a_i \le 10^9$

Output

Print the number of weird intervals on one line. An interval is a non-empty contiguous subsequence, and two intervals with a different start or end position count separately even when their values are the same.

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], so the answer is 15. Two different intervals hold the single record 4, and both of them are counted.

Examples4

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