题目描述

小蓝作为一个二维生物快乐地生活在二维坐标系中，他最近得到了一块土地，他想把这块土地整平用于修建花园。具体来说，这块土地从左到右长度为 $n$ 格，第 $i$ 格的高度为 $h_i (i \in [1, n])$。小蓝每次可以花费代价 $w$ 将一段连续的区间 $[l, r]$ 中的土地高度都变为 $w$，其中 $l \leq r$，这段区间需要满足以下三组条件之一：

1. $l = 1$, $r < n$，且对于 $i \in [l, r]$ 有 $h_i \neq h_{r+1}$，此时代价 $w = h_{r+1}$；
2. $l > 1$, $r = n$，且对于 $i \in [l, r]$ 有 $h_i \neq h_{l-1}$，此时代价 $w = h_{l-1}$；
3. $1 < l \leq r < n$，$h_{l-1} = h_{r+1}$，且对于 $i \in [l, r]$ 有 $h_i \neq h_{l-1}$，此时代价 $w = h_{l-1} = h_{r+1}$。

小蓝希望在若干次操作之后将这块土地整平，即所有格子的高度都相等，并且花费的代价总和最小。请你帮助他计算一下最小花费。

输入格式

输入的第一行包含一个正整数 $n$。

第二行包含 $n$ 个正整数 $h_1, h_2, \ldots, h_n$，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

8
5 4 10 4 20 5 4 5

10

提示

【样例说明】

选择将土地高度都变为 $5$，只需操作两次：将 $[2,5]$ 和 $[7,7]$ 的高度都变为 $5$，代价总和为 $10$。

【评测用例规模与约定】

对于 50% 的评测用例，$1 \leq n \leq 5000$；

对于所有评测用例，$1 \leq n \leq 10^6$，$1 \leq h_i \leq 10^6$。