Maximizing Graph Score

You are given n non‐negative integers \(x_1,x_2,\dots,x_n\). For any connected undirected graph \(G\) on n nodes with vertices labeled \(1,2,\dots,n\), define its score as

[ \text{score}(G)=\sum_{1\le i< j\le n} \text{dist}_G(i,j)x_i x_j, ]

where \(\text{dist}_G(i,j)\) denotes the shortest path distance between nodes \(i\) and \(j\) in \(G\). Your task is to choose a connected graph \(G\) on the given n vertices (by selecting its edges) so that its score is maximized, and then output the maximum score.

Observation: Every connected graph on n vertices has an underlying spanning tree. In a tree the distance between two vertices is the number of edges in the unique simple path connecting them. Hence, one may restrict to trees. In fact, by a careful choice of the tree structure (i.e. by choosing an optimal spanning tree), one can maximize the score.

A useful way to represent the score for any tree is as follows. If the tree is a path (chain) with vertex order \(b_0,b_1,\dots,b_{n-1}\) (which is always possible by reordering the vertices arbitrarily, since the input weights \(x_i\) can be assigned to any labeled vertex), then the distance between vertices in positions \(i\) and \(j\) is \(|i-j|\) and the score can be written as

[ \text{score} = \sum_{i=0}^{n-2} \left( \Big(\sum_{j=0}^{i}b_j\Big)\Big(\sum_{j=i+1}^{n-1}b_j\Big) \right). ]

It turns out that the optimal strategy is to choose a spanning tree that is a path and then determine an optimal ordering \(b_0,b_1,\dots,b_{n-1}\) of the given weights. One can prove that an optimal ordering is obtained by:

1. Sort the numbers in non‐decreasing order: \(a_0 \le a_1 \le \dots \le a_{n-1}\).
2. If \(n \ge 2\) then set the two endpoints of the path as \(a_{n-1}\) (the largest) and \(a_{n-2}\) (the second largest).
3. Place the remaining \(n-2\) numbers (if any) in increasing order between the endpoints.

In other words, if we denote the final ordering as:

[ b = [a_{n-1}] \mathbin{+} [a_0,a_1,\dots,a_{n-3}] \mathbin{+} [a_{n-2}], ]

then the maximum score is

[ \max \text{score} = \sum_{i=0}^{n-2} \Big(\sum_{j=0}^{i}b_j\Big)\Big(\sum_{j=i+1}^{n-1}b_j\Big). ]

</p>

Input Constraints: n is a positive integer. When n = 1, the output is 0.

Note: All formulas are rendered in \(\LaTeX\) format.

inputFormat

The first line contains a positive integer n (1 ≤ n ≤ 10⁵), representing the number of nodes. The second line contains n non‐negative integers \(x_1, x_2, \dots, x_n\) separated by spaces.

outputFormat

Output a single integer, which is the maximum score among all connected undirected graphs on n nodes.

sample

2
5 10

50