Fish Between the Guards

Time limit: 2000 msMemory limit: 256 MB

Gats has arranged $N$ bowls in a row. Bowl $i$ contains $P_i$ fish, and every bowl contains a different number of fish.

Gats chooses two different bowls $L$ and $R$ , where $L < R$ , and places one guard cat at each of them. This placement is well-framed if every bowl $i$ satisfying $L < i < R$ has a fish count strictly between the counts at the two guarded bowls. Formally, it must satisfy

\min(P_L,P_R) < P_i < \max(P_L,P_R)

for every $i$ such that $L < i < R$ .

If $R=L+1$ , there are no bowls between the guards, so the placement is automatically well-framed.

Count the number of well-framed pairs $(L,R)$ .

Input

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

The second line contains $N$ integers . They form a permutation of the set .

Output

Print one integer: the number of well-framed pairs $(L,R)$ .

Samples

Sample 1

Input

5
3 1 4 5 2

Output

The five well-framed placements are $(1,2)$ , $(2,3)$ , $(2,4)$ , $(3,4)$ , and .

Fish Between the Guards

Input

Output

Samples

Sample 1

Submit

Submissions

Sample 2

Sample 3