题目描述：

给定正整数列 $P_1, P_2,\dots, P_N$。考虑数列 $a_1, a_2, \dots, a_N$，它满足下列条件

• $a_i = -1, 0 \ 或 \ 1$
• 对于 $1 \le i \le N$ 有 $a_1 + \dots + a_i \ge 0$

求 $\sum_{1 \le i \le N} a_i P_i$ 的最小值。

限制

• $1 \le N \le 2 \times 10^5$
• $1 \le P_i \le 10^9$

输入格式：

$N$
$P_1 \ P_2 \ \dots \ P_N$

输出格式：

输出答案。

样例：

8
2 5 4 3 7 1 8 6

16