| 问题描述 |
|---|
lyf非常喜欢钢铁侠，于是励志做一个头铁的人，打比赛时以某道题开始，沿着正序或者逆序做题。例如某场比赛有A、B、C、D、E五题，如果lyf选择了从D题开始逆序做题，那么做题顺序就是D、C、B、A、E；如果lyf选择从C题开始正序做题，那么做题顺序就是C、D、E、A、B。 现在已知lyf每道题都是一次提交就通过，于是每道题的罚时计算就是从比赛开始到该题做出来的时间。lyf希望所有题目的罚时总和尽可能小，问该最小值是多少？ |
| 输入描述 |
多组案例。一个正整数T，表示案例的数量。（T<=500000） 每组案例中，先是一个正整数n，表示题目的数量。（n<=500000，并且保证所有案例中的n的总和不大于500000） 然后是n个数字a1~an，表示每道题花费的时间。（ai<=500000） |
| 输出描述 |
针对每组案例，输出一个整数，表示最小的罚时值。 每组案例输出完都要换行。 |
| 样例输入复制样例 |
2 5 1 5 3 4 2 10 10 4 6 2 5 9 3 7 8 1 |
| 样例输出 |
36 277 |
| 相关 |