该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

大样例下载

题目描述

你有一个圆筒状容器，这个容器有无限高且不封顶，其内部被 $n$ 块挡板划分为 $n$ 个底面积为 $1$ 的部分。第$i$块挡板高度为 $h_i$。根据物理学，若挡板 $i$ 左右两侧液体高分别为 $x,y$ 且 $x,y>h_i$，则 $x=y$。

现在你要向这个容器内加水，对于每个$i$，你想求若要求第$i$个挡板和第$(i\mod n)+1$个挡板中间为空（即液体高度为$0$），容器最多能装多少水。

输入输出格式

输入格式

第一行一个整数 $T$，表示数据组数。对于每组数据：

第一行一个整数 $n$，接下来一行 $n$ 个整数$h_i$，表示第$i$个挡板的高度。

输出格式

对于每组数据，一行 $n$ 个整数，表示要求第$i$个挡板和第$(i\mod n)+1$个挡板中间为空时容器最多能装多少水。

输入输出样例

4
4
1 2 3 4
5
5 3 1 5 2
6
3 4 2 6 1 5
7
1 2 1 4 2 3 5

6 7 9 6
16 14 14 17 17
21 20 20 21 21 21
17 17 17 21 21 22 17

1
8
743520124 285875297 764818337 244572230 660281242 592710694 226564737 319933543 

4746996041 4746996041 4372737446 4372737446 4585734814 3946811706 3946811706 4040180512

样例解释

这里仅解释样例 1 第一组数据

数据范围

记$N=\sum n$。

$2 \leq n,N \leq 10^6 ,1 \leq h_i \leq 10^9 ,1 \leq T \leq 10^5$。

特殊性质$A$：保证$h_i$单调不降。

特殊性质$B$：数据拿脚造数据随机。