Cats and the Threaded Posts

Time limit: 2000 msMemory limit: 256 MB

Gats has placed $N$ scratching posts in a row and tied a long thread among them. The $i$ -th post has height $H_i$ , and all post heights are distinct.

Gats chooses two posts with indices $L$ and $R$ , where $1 \le L < R \le N$ . This choice forms a smooth span if every post strictly between them has a height strictly between the two endpoint heights. In other words, for every index $i$ satisfying $L < i < R$ ,

\min(H_L,H_R) < H_i < \max(H_L,H_R).

If $R=L+1$ , there are no inner posts, so the span is considered smooth.

Count the number of smooth spans Gats can choose.

Input

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

The second line contains $N$ pairwise distinct integers (), where is the height of the -th post.

Output

Print one integer: the number of smooth spans $(L,R)$ .

Samples

Sample 1

Input

5
4 1 3 5 2

Output

The valid endpoint pairs are $(1,2)$ , $(2,3)$ , $(2,4)$ , $(3,4)$ , and .

Cats and the Threaded Posts

Input

Output

Samples

Sample 1

Submit

Submissions

Sample 2

Sample 3