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

题目描述

题面 PDF
    题面 PDF：【点击下载】
\sf Everything\ that\ kills\ me\ makes\ me\ feel\ alive.

               —— Counting\ Stars,\ \text{OneRepublic}
氧气少年参加了一场比赛。

这场比赛有 n 名裁判，第 i 名裁判给氧气少年的分数为 a_i。

但是氧气少年对自己的得分不满意，他可以进行下面的操作最多一次：
  • 任意选定一名裁判，将他给出的分数加 1。

氧气少年的最终得分为：所有裁判给出的分数中，去掉一个最高分和一个最低分后的平均值。

请求出氧气少年的最终得分的最大值。为了便于表示，请输出得分最大值 \times(n-2) 的值。

输入描述:

第一行包含一个整数 T(1\leq T \leq 10^5)，表示测试用例的组数。

对于每组测试用例：

第一行包含一个整数 n(3\leq n\leq 2\cdot 10^5)，表示裁判的数量。
第二行包含 n 个整数 a_1\dots a_n(0\leq a_i\leq 10^9)。

保证对于所有的测试用例，n 的总和不超过 2\cdot 10^5。

输出描述:

对于每组测试用例：
仅输出一行，包含一个整数，表示答案。
示例1

输入

复制 
2
3
1 2 3
4
1 2 2 3

输出

复制 
3
5