Minimize Segment Partition Contribution Sum

Given a sequence a of length n, you are required to partition the sequence into one or more non-empty contiguous segments.

For each segment \([l, r]\), its contribution is defined as \[ w = \Bigl(\min_{i=l}^{r} a_i\Bigr) \times \Bigl(\max_{i=l}^{r} a_i\Bigr). \] Your task is to determine a partition such that the sum of contributions \[ \sum w \] is minimized. Output this minimum sum.

inputFormat

The first line contains an integer n representing the length of the sequence.

The second line contains n space-separated integers representing the sequence a.

outputFormat

Output a single integer which is the minimum total contribution achievable by an optimal partition of the sequence.

sample

3
1 2 3

3