Problem 4364: Hai, hai cu trăsioara

„Hai, hai cu trăsioara, până-n deal la Mărioara” — Source

You are given an array $v$ of $N$ integers.

Define vavale (noun, plural văvăi) as a subset of 5 indices $i_1$ , $i_2$ , $i_3$ , $i_4$ , $i_5$ such that the following conditions are met:

$1 \le i_1 \lt i_2 \lt i_3 \lt i_4 \lt i_5 \le N$
$v_{i_1} \gt v_{i_2} \lt v_{i_3} \gt v_{i_4} \lt v_{i_5}$
$v_{i_1} \gt v_{i_3} \lt v_{i_5}$

Informally, you could think of a vavale as the concatenation of a valley formed from $i_1$ , $i_2$ , $i_3$ with a valley formed from $i_3$ , $i_4$ , $i_5$ , with the extra condition that $v_{i_3}$ is strictly smaller than $v_{i_1}$ and $v_{i_5}$ (in a valley the middle element is strictly smaller than its two endpoints).

Task

Count the number of văvăi modulo $2^{64}$ .

Input data

The first line contains the integer $N$ . The second line contains $N$ integers, the array $v$ .

Output data

Output the number of văvăi modulo $2^{64}$ (a nonnegative integer).

Constraints and clarifications

$5 \le N \le 200\ 000$
$1 \le v_i \le 10^9$

Example 1

stdin

7
9 4 7 5 7 2 8

stdout

Explanation

The $5$ văvăi are formed of the following indices:

$1$ , $2$ , $3$ , $4$ , $7$ ;
$1$ , $2$ , $3$ , $6$ , $7$ ;
$1$ , $2$ , $4$ , $6$ , $7$ ;
$1$ , $2$ , $5$ , $6$ , $7$ ;
$1$ , $4$ , $5$ , $6$ , $7$ .

Example 2