Mountain

Interview

Time limit1sMemory limit1024 MB

Summary

Count the contiguous subarrays that never decrease before a peak and never increase after it, with N up to 500000.

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

Problem

Onjo likes climbing mountains. So Onjo wants to find as many mountain shapes as possible in a sequence $A_1, \cdots, A_N$ of length $N$ .

Problem

Take a contiguous subsequence $A_l, \cdots, A_r (l \le r)$ of $A$ . It is a mountain shape if there is an integer $l \le k \le r$ such that $A_l \le A_{l+1} \le \cdots \le A_k \ge \cdots \ge A_{r-1} \ge A_r$ holds.

Help Onjo. Given the sequence $A$ , count the contiguous subsequences of $A$ that are mountain shaped.

Input

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

The second line contains $N$ integers $A_1, \cdots, A_N$ separated by spaces.

Output

Print the number of contiguous subsequences of $A$ that are mountain shaped.

Constraints

$1 \le N \le 500000$

For each $i$ ( $1 \le i \le N$ ), $1 \le A_i \le 1000000000$ .

Examples3

Example 1
Input
```
5
1 2 3 2 3
```
Expected output
```
12
```
Example 2
Input
```
3
100 100 100
```
Expected output
```
6
```
Example 3
Input
```
7
1 1 3 3 2 2 4
```
Expected output
```
24
```