# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* raysh07

*apoorv_me*

**Tester:***iceknight1093*

**Editorialist:**# DIFFICULTY:

TBD

# PREREQUISITES:

None

# PROBLEM:

For an array B of length N, define f(B) = \sum_{i=1}^{N-1} (B_i + B_{i+1}).

You’re given an array A. Find the maximum possible value of f(A) if A can be rearranged as you please.

# EXPLANATION:

Let’s rewrite f(A) a bit to bring it to a nicer form.

Here, notice that (A_1 + A_2 + \ldots + A_N) is just the sum of the array, and is constant irrespective of how it is rearranged.

So, if we let S = 2\cdot (A_1 + A_2 + \ldots + A_N), we have f(A) = S - A_1 - A_N, with the rearrangement only allowing us to choose the values of A_1 and A_N.

Since our aim is to maximize f(A), clearly it’s best to put the two smallest values in A at these positions.

That is, let m_1 and m_2 denote the smallest and second-smallest elements of A.

Then the answer is exactly

Finding S, m_1, m_2 can all be done with a simple loop across the array.

# TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

# CODE:

## Editorialist's code (Python)

```
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
a.sort()
print(2*sum(a) - a[0] - a[1])
```