Gats and the Single Wobble

Time limit: 2000 msMemory limit: 256 MB

Gats practices jumping between platforms connected by branches. The $N$ platforms and their $N-1$ branches form a tree, so there is a unique route between every two platforms. Platform $i$ has height $H_i$ , and platforms joined directly by a branch always have different heights.

For two distinct platforms $s$ and $t$ , write their route as

v_0=s, v_1, \ldots, v_k=t.

An internal platform $v_j$ , where $1 \le j < k$ , is a wobbly landing if Gats continues in the same vertical direction after landing. More precisely, it is wobbly if either

H_{v_{j-1}} < H_{v_j} < H_{v_{j+1}}

H_{v_{j-1}} > H_{v_j} > H_{v_{j+1}}.

Thus, a wobbly landing occurs when two consecutive jumps are both upward or both downward.

A route is called a one-wobble route if it contains exactly one wobbly landing. Routes are considered without direction, so the pair $\{s,t\}$ is the same as the pair $\{t,s\}$ .

Count the unordered pairs of distinct platforms whose route is a one-wobble route.

Input

The first line contains an integer $N$ ( $1 \le N \le 2 \times 10^5$ ), the number of platforms.

The second line contains $N$ integers (), where is the height of platform .

Output

Print one integer: the number of unordered pairs of distinct platforms whose route is a one-wobble route.

Samples

Sample 1

Input

Output

The one-wobble routes are the four high-to-low leaf pairs $(2,3)$ , $(2,5)$ , $(4,3)$ , and $(4,5)$ .

Gats and the Single Wobble

Input

Output

Samples

Sample 1

Submit

Submissions

Sample 2