C-Sequence Cost_牛客周赛 Round 122

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小苯的面前有一个长度为 $n$ 的序列 $a$ ，他现在需要花费： $a_1+a_2+a_3+...+a_n$ 的代价拿走 $a$ 序列，但为了最小化代价，他可以提前做任意次以下操作：

$\hspace{23pt}\bullet$ 选择一个区间 $l, r\ (1 \leqq l \leqq r \leqq n)$ ，花费区间最大值的代价，将区间中所有值均变为最小值。

$\hspace{23pt}\bullet$ 形式化的即，令：
$mx=\max(a_l,a_{l+1},a_{l+2},...,a_r), mn=\min(a_l,a_{l+1},a_{l+2},...,a_r)$
$\hspace{15pt}$ 接着花费 $mx$ 的代价，对所有 $i$ 执行 $a_i\leftarrow mn, (l \leqq i \leqq r)$ 。

$\hspace{15pt}$ 你的任务就是求出小苯拿走 $a$ 序列的最小花费。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行一个正整数 ，表示序列  的长度。
第二行  个整数 ，表示序列 。

除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每组测试数据：

在单独的一行输出一个整数表示拿走  序列的最小代价。

示例1

输入

复制

输出

复制

6
2