Description

You are given array $a_1, a_2, \dots, a_n$ . You need to split it into some subsegments (so every element is included in exactly one subsegment).

The weight of a subsegment $a_l, a_{l+1}, \dots, a_r$ is equal to $(\min_{i=l}^{r}a_i)\times(\max_{i=l}^{r}a_i)$ . The weight of a partition is a total weight of all its segments.

Find the partition of minimal weight.

Input Format

The first line contains an integer $n$ — the length of the array $a$ .

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ — the array $a$ .

Output Format

Print a single integer — the minimal weight among all possible partitions.

4
-1 2 -1 2

-4

6
-3 4 -9 1 2 4

-48

Hint

The optimal partition in the first example is next: $-1$ $2$ $\bigg|$ $-1$ $2$ .

The optimal partition in the second example is next: $-3$ $4$ $\bigg|$ $-9$ $1$ $2$ $4$ .

Constraints

This problem uses subtask scoring.

For $100\%$ of the data, $1 \le n \le 10^6$, $-10^6 \le a_i \le 10^6$.