Skip to content
TheChatArchiveThe Chat Archive
DeepSeekDeepseek v3.2· deepseekHugging Face Frontier Reasoning Traces

Little Pandey and GJ are coding buddies - since they are the part of ACM ICPC team…

  1. User

    Little Pandey and GJ are coding buddies - since they are the part of ACM ICPC team together. But, GJ is fed up of Pandey's weird coding habits - like using editors which are slow, and irritating. Importantly, GJ believes that Pandey over-complicates a task while solving it.

    So, to prove his point he gives Pandey a trivial task to solve. He gives him N numbers, and tells him to repeat the following operation. Pandey can choose two numbers and replace them with one number, equal to their sum. It takes some time of course. It turns out that the needed time is equal to a new number.

    For example, if Pandey sums 2 and 3, he gets a number 5 and it takes him 5 units of time.

    Now, GJ asks Pandey to keep summing numbers till there is only one number left in the array. GJ is sure that Pandey will do it in the worst possible way - he will maximize the amount of time taken.

    GJ wants to predict the total time Pandey will take to complete this task. Unfortunately, GJ's slow mathematical skills are failing him, so he calls you for help. You know what you need to do next! Input format: The first line contains an integer T, denoting the number of test cases. Then, T test cases follow.

    Each test case consist of two lines. The first line contains an integer N, denoting the size of the array chosen by GJ. The second line contains contain N integers, denoting the initial numbers in an array.

    Output format: For every array, find out the total time taken by Pandey to finish the described process.

    Constraints: 1 ≤ T ≤ 10^2 1 ≤ N ≤ 10^6 1 ≤ Ai ≤ 10^7 - where Ai denotes the i-th initial element of an array. The sum of values of N in one test file won't exceed 5 * 10^6.

    SAMPLE INPUT 2 4 4 2 1 3 5 2 3 9 8 4

    SAMPLE OUTPUT 26 88

  2. DeepSeek Assistant

    We need to read problem statement carefully. It describes a process: we have N numbers. We repeatedly choose two numbers, replace them with their sum, and the time taken for that operation equals the sum (the new number). We keep doing until one number left. Pandey will do it in the worst possible way, i.e., to maximize total time taken. GJ wants to predict the total time taken.

    We need to compute the maximum total time possible by choosing the order of pair merges.

    We have initial numbers a1..aN. We can merge any two at each step. When we merge x and y, we add x+y to total time, and we replace them with a new number s = x+y. This process is like building a binary tree where leaves are initial numbers, internal nodes are sums of children, and the total time is sum of all internal nodes (i.e., sum of values of all internal nodes). In typical "optimal merging" problem (like Huffman coding) we want to minimize total cost, which is sum of internal nodes when we merge smallest first (like building Huffman tree). But here we want to maximize total cost.

    We need to find maximum possible sum of internal nodes (or total time) given we can choose order of merging.

    Observation: The process is essentially the same as building a full binary tree on leaves (since merging two at a time until one). The total cost is sum of all internal node values, where each internal node's value is the sum of leaves in its subtree. So total cost = sum over internal nodes of sum of leaves in its subtree.

    If we denote leaf values as a_i, and we assign them to leaves of a full binary tree with N leaves (binary tree where each internal node has exactly two children). The total cost = sum_{internal node v} S(v), where S(v) is sum of leaves in subtree.

    Total cost can be expressed in terms of leaf contributions: each leaf a_i contributes to the sum of S(v) for each internal node that is an ancestor of that leaf. So total cost = sum_i a_i * (depth of leaf? Actually number of times that leaf is included in ancestor sums). For each leaf, if we denote the number of internal nodes on path from leaf to root (excluding leaf itself) as k_i, then total cost = sum_i a_i * k_i. For a binary tree where root is the final sum (internal node), the root is also counted (internal node) but the root is ancestor of all leaves. So k_i = number of internal nodes that are ancestors of leaf i. In a full binary tree with N leaves, the total number of internal nodes is N-1. Each leaf's ancestor count is the number of internal nodes on its path to root. The root is ancestor of all leaves, etc.

    Goal: maximize sum_i a_i * k_i subject to we can choose any full binary tree shape? And we can also assign leaf values to leaves arbitrarily? Since we can choose any order of merging, that corresponds to a binary tree (the order of merges). In such a tree, the leaf assignment to positions is determined by which numbers are merged when. But we can assign any leaf to any leaf position because we can merge any pair at any step. Effectively, we can permute the initial numbers arbitrarily among leaves, as we decide which ones to merge. So we can choose any full binary tree shape and any mapping of numbers to leaves. So we need to maximize sum_i a_i * k_i over all binary trees with N leaves and over all assignments of numbers to leaves.

    We want to maximize total internal sum. For minimization problem (Huffman), we combine smallest first to minimize cost. For maximization, we should combine largest first? But careful: In Huffman, total cost is sum of all internal nodes; the minimization solution is to combine smallest two repeatedly. For maximization, intuitively we would combine largest two first? Let's test small cases.

    Case N=2: numbers a,b. Only one merge: cost = a+b. So total = a+b, regardless of order.

    Case N=3: numbers a,b,c. We need to merge two then merge result with third. Suppose we merge x and y first, cost = x+y, then merge (x+y) with z, cost = x+y+z. Total = (x+y) + (x+y+z) = 2x+2y+z. So total time depends on which two we merge first. To maximize total, we want to choose as x and y the two largest? Then z is smallest. Let a≥b≥c. Option1: merge a,b first: total = 2a+2b+c. Option2: merge a,c first: total = 2a+2c+b. Option3: merge b,c first: total = 2b+2c+a. Since a≥b≥c, 2a+2b+c vs 2a+2c+b: subtract: (2a+2b+c)-(2a+2c+b)= (2b+c)-(2c+b)= b-c >0. So merge largest two gives highest. Compare with b,c first: 2a+2b+c vs 2b+2c+a: difference = (2a+2b+c)-(2b+2c+a)= a-c >0. So indeed merging largest two first maximizes total.

    For N=4: we can simulate or derive formula. Let's test numbers 4,2,1,3 (sample). If we follow rule: always merge two largest? Let's compute. Numbers: 4,3,2,1. Merge 4+3=7 cost7 -> remaining: 7,2,1. Merge 7+2=9 cost9 -> remaining: 9,1. Merge 9+1=10 cost10 -> total = 7+9+10 = 26. That matches sample output 26. Sample output for first case is 26. So indeed worst possible time for sample is 26, which corresponds to merging largest first.

    Second sample: 2,3,9,8,4. Sort: 9,8,4,3,2. Merge 9+8=17 cost 17 -> remaining: 17,4,3,2. Merge 17+4=21 cost21 -> remaining: 21,3,2. Merge 21+3=24 cost24 -> remaining: 24,2. Merge 24+2=26 cost26 -> total = 17+21+24+26 = 88? Let's sum: 17+21=38, +24=62, +26=88. Yes matches sample output. So the maximum total time is achieved by repeatedly merging the two largest numbers.

    But we must verify that this greedy algorithm indeed yields maximum total. This is akin to the opposite of Huffman coding: we want to maximize sum of internal nodes, which is done by merging the two largest numbers at each step. This is sometimes called "maximization merging" and it's known to be optimal by a similar exchange argument: if you have two numbers that are not the largest combined, swapping to combine larger earlier increases total cost because it adds the larger sum to more subsequent merges.

    We can prove: For any binary tree, the total cost = sum over all leaves a_i * (number of internal nodes on path). That is equivalent to sum of leaf weights times depth of leaf in the tree (if we consider depth counting internal nodes). The total number of merges is N-1, but the contributions are multiplied. To maximize, we want larger weights to have higher multiplier (i.e., be merged later? Wait: In the sum, leaf with larger multiplier contributes more. In a binary tree, leaves that are merged later (i.e., are combined only at later stages) have lower depth? Actually think: In a merge process, if we combine two numbers early, they become part of a larger sum that is then used in later merges. The leaf's value gets added to all internal nodes above it. The leaf that remains as an individual leaf longer (i.e., is merged only near the end) will have fewer ancestors? Let's see: In the tree, root is the final merge. Leaves that are merged later are deeper? Actually, the merge tree: leaves are initial numbers. Each internal node corresponds to a merge. The leaf that is merged only at the final step is directly combined with the accumulated sum of all others at the root. For example, in N=3, with numbers a,b,c. If we merge a and b first, then merge that with c. The tree: root is merge of (a+b) and c. Leaves: a, b, c. For leaf c, its ancestors: only root (since c is directly merged at the final step). So depth (internal nodes) = 1. For leaves a and b, they are merged first to form internal node (a+b), which is then merged at root. So ancestors for a: internal node (a+b) and root -> depth 2. So larger multiplier for a and b. So leaves that are merged earlier (i.e., part of early merges) get higher multipliers because they appear in more sums along the way. So to maximize total, we want larger values to be merged earlier (so they have higher multipliers), and smaller values to be merged later (so they have smaller multipliers). That's exactly what "merge largest first" does: the two largest numbers are combined early, so they become part of a big number that then gets used in later merges, thus those large values get multiplied by many subsequent merges. The smallest numbers are merged later, getting fewer multipliers. So greedy merging largest first yields maximum sum.

    Thus solution: For each test case, we repeatedly take two largest numbers, compute sum, add to total, insert sum back into the multiset. But N can be up to 1e6, and total N across test cases up to 5e6. Direct use of priority queue (max-heap) with O(N log N) would be okay? 5e6 log 5e6 ~ 5e6*22 = 110e6, maybe okay in C++ but T could be up to 100, but sum N across file is ≤5e6, so total operations across all test cases is O( sum N log N )? Actually each merge reduces size by 1, so we do N-1 merges per test case. So total merges across all test cases = sum(N_i) - T. Since sum N_i ≤5e6, total merges ≤5e6. For each merge we do pop two and push one: O(log size). So total O( sum N log N ) which with sum N=5e6, worst-case log N ~ 23, so about 115 million heap operations. That's okay in C++ with fast I/O, but we need to be careful about time. However, there might be an even faster approach: Since we just need the total cost, we can compute it using a formula? Possibly we can derive a closed form: The greedy process is basically building a tree where at each step we combine two largest. The total cost can be computed as sum_{i=1}^{N-1} s_i where s_i are the sums produced. That's exactly the sum of all merges. But we can compute without simulation? Possibly using sorting and cumulative sums? Let's think.

    If we always merge two largest, the process is analogous to building a "max-Huffman" tree. There might be an expression: total cost = sum_{k=1}^{N-1} (sum of top two at each step). But we can compute using a data structure efficiently. However, given constraints up to 5e6 total N, O(N log N) should be acceptable, especially using a binary max-heap (std::priority_queue with max) or using a multiset? But using a max-heap is efficient.

    But we need to ensure that we use 64-bit integers, as sums can be large. Maximum values: Ai up to 1e7, N up to 1e6, sum of all numbers up to 1e13? Actually 1e7 * 1e6 = 1e13. And total cost can be larger because each sum is added multiple times. In worst case, think about values: all equal to 1e7, merging largest first leads to something like: The total cost = sum_{k=1}^{N-1} sum of two largest at step. This might be on order of (N) * (something). More precisely, if we take all numbers equal, the process is similar to building a tree, total cost = (N-1)* sum? Let's compute: all equal to x. Merge two largest (both x) -> sum 2x, cost 2x. Now numbers: 2x, x (N-1 of them? Actually after first merge we have N-1 numbers: one 2x and (N-2) copies of x. Next merge two largest: 2x and x -> sum 3x, cost 3x. So cost sequence: 2x,3x,4x,...? Let's simulate: step 1: (x,x) -> 2x, cost 2x, multiset: {2x, x,...(N-2)x} Step 2: merge 2x and x -> 3x, cost 3x, multiset: {3x, x, ...(N-3)x} Step 3: merge 3x and x -> 4x, cost 4x... So after i merges (i from 1 to N-1), the cost is (i+1)*x? Actually first cost =2x (i=1), second=3x, third=4x,... up to N-th? There are N-1 merges, last merge merges (N-1)*x? Let's think: After N-2 merges, we have two numbers: one is (N-1)x? Actually after each merge, the largest number grows. At step k (starting at 1), the largest number is (k+1)x (since initially largest = x; after first merge we have largest=2x; after second merge largest=3x; after i merges largest = (i+1)x). The next largest is x (since we always merge the largest with a leaf x). So the sum at step i (i from 1 to N-1) is ((i+1)x + x) = (i+2)x? Wait careful: At step i, before merge i, we have numbers: one large number = (i+1)x? Let's define state after i-1 merges. At start (0 merges): we have N copies of x. After 0 merges, largest = x. After 1 merge: we have numbers: 2x, and N-2 copies of x. So largest = 2x. After 2 merges: numbers: 3x, and N-3 copies of x. So after k merges, numbers: (k+1)x, and N-1-k copies of x? Actually after k merges, we have N-k numbers. The largest is (k+1)x, and the remaining N-k-1 numbers are x each. So before the (k+1)-th merge (i.e., merge index = k+1), we have numbers: largest = (k+1)x, and the next largest is x. So sum = (k+1)x + x = (k+2)x. So cost of (k+1)-th merge is (k+2)x. Then after merge, we have (k+2)x as largest and N-(k+2) copies of x.

    Thus merge number j (1-indexed) has cost (j+1)x? Let's test: j=1 -> (1+1)x =2x correct. j=2 ->3x correct. j=N-1 -> (N-1+1)x = N x? Wait j=N-1 gives cost (N-1+1)x = Nx. But does that match? At last merge, we have two numbers: after N-2 merges, we have numbers: largest = (N-1)x? Actually after N-2 merges, numbers: (N-1)x, and one x? Let's check: After k merges, number of numbers = N - k. We want to end with 1 number after N-1 merges. So after N-2 merges, we have 2 numbers: largest = (N-1)x? Because k = N-2 gives largest = (N-2+1)x = (N-1)x. And the other number is x? According to pattern, after N-2 merges, we have (N-1)x and one x? But initial copies: we start with N copies of x. Each merge consumes one x copy? Actually each merge replaces two numbers with one, so total count reduces by 1. But the large number accumulates all merged x's. After merging the large number with a single x each time, the large number becomes sum of all merged x's plus the base. After first merge, large number = 2x (two x's). After second merge, large number = 3x (since adds another x). So after N-2 merges, large number = (N-1)x (since it has been merged with (N-2) additional x's? Wait: It started as two x's merged to become 2x, then each subsequent merge added one x, so after first merge: 2x (merged 2). After second merge: 3x (merged 3). After third merge: 4x (merged 4). So after k merges, large number = (k+1)x. So after N-2 merges, large number = (N-2+1)x = (N-1)x. And then we have one remaining x? At start, N copies. After each merge, we use one copy of x? Actually we used the large number and one x to merge, consuming one x. Initially, after 0 merges we have N copies. After 1 merge: we used two x's to create 2x, so we have N-2 copies left plus 2x? That is N-1 total numbers? Wait careful: Numbers after merge: we remove two numbers (both x) and add 2x, so total count reduces by 1: from N to N-1. Among these N-1 numbers, one is 2x, the rest N-2 are x. So we still have N-2 copies of x. After second merge: we merge 2x and one x, remove them, add 3x -> count reduces to N-2. Among these, one is 3x, the rest N-3 are x. So after k merges, count = N - k. The large number is (k+1)x, and there are N - k - 1 copies of x. So after N-2 merges, count = N - (N-2) = 2. So numbers: large number = ((N-2)+1)x = (N-1)x, and copies of x = N - (N-2) - 1 = 1 copy of x. So last merge (N-1) will merge (N-1)x and x to get Nx, costing Nx. So total cost = sum_{j=1}^{N-1} (j+1)x = x * [sum_{j=2}^{N} j]? Actually j+1 from j=1 to N-1 gives values 2,3,...,N. So sum = x * ( (2+N)(N-1)/2? ) = x * ( (N+2)(N-1)/2 ). For large N, this is ~ N^2 * x/2. With x=1e7, N=1e6, N^2=1e12, times x=1e7 yields 1e19, which exceeds 64-bit? 1e19 is > 9e18 (max 64-bit unsigned is 1.84e19, signed 9.22e18). Actually 1e19 > 9.22e18, so might overflow 64-bit signed. But maybe we can use unsigned 64-bit? Unsigned max is 1.84e19, so 1e19 fits? 1e19 is 10^19, which is 1e19 > 1.84e19? Wait: 1.84e19 is 1.84*10^19 = 18.4e18 = 1.84e19. 10^19 = 1e19, which is less than 1.84e19, so fits in unsigned 64-bit. But many online judges use 64-bit signed long long. Typically they expect using 64-bit signed, but might need unsigned or __int128? But sample values are small. However constraints: N up to 1e6, Ai up to 1e7, worst-case total cost: we can compute more accurately.

    Let's compute worst-case total cost for all maximum numbers. Use formula: total = sum of all merge sums. In greedy merging largest first, the order of merges is deterministic (like we always pick two largest). The cost can be expressed as sum_{i=1}^{N-1} (sum of two largest at that step). We can compute using a priority queue or maybe using a variant of sorting and prefix sums to get O(N log N) but we could also compute via formula if we derive the pattern. But the pattern depends on the values, not just sorted order? Actually if we always take two largest, we can simulate efficiently using two queues (like for Huffman, we can use two sorted lists to achieve O(N) after sorting). Since we only need total, we can use a "two queues" method: sort the numbers descending. Then we maintain two queues: one for original numbers (sorted descending) and one for merged sums. At each step, we need the two largest among the heads of both queues. This can be done in O(N). That would be O(N log N) due to sorting, but after sorting O(N) for merges. Since total N sum is 5e6, sorting is O(N log N) overall, which might be okay. But we can consider both.

    Now, we need to confirm that merging largest first indeed yields the maximum total cost. Let's attempt to prove: The problem is symmetric to minimizing sum of internal nodes, known as Huffman coding, where the optimal is to repeatedly merge the two smallest. By exchanging two leaves with different weights, we can prove that to maximize, we should put larger weights higher in the tree (i.e., give them larger multipliers). In a binary tree, the sum of leaf weight times depth (number of internal nodes) is minimized when larger weights are closer to root (smaller depth) and maximized when larger weights are farther from root (larger depth). Wait, in Huffman we minimize total cost, which is sum leaf * depth (if we define depth as number of merges or path length). In Huffman, we want to minimize weighted path length; we put larger weights shallower (closer to root). For maximization, we want larger weights deeper (farther from root). But in our merging process, the total cost is sum_{internal nodes} sum of leaves in subtree. This is not exactly the same as weighted path length? Let's connect: In binary tree where each internal node value is sum of leaves in its subtree, the total sum of internal nodes = sum_{leaves} leaf * (number of internal nodes on path from leaf to root). That's exactly leaf * depth_i, where depth_i counts internal nodes on path (including root). So it's weighted depth where depth = number of internal nodes (i.e., number of merges the leaf participates in). In such a tree, root depth = 1 for all leaves? Actually root depth counts as 1 for all leaves. So total cost = sum leaf * depth_i. So it's the same as "total weighted depth". In Huffman, we minimize sum leaf * depth, where depth is number of edges (or number of bits). Usually Huffman tree is full binary tree where internal nodes have two children, and we minimize sum leaf weight * depth. In our definition depth counts internal nodes (like number of merges). If we consider edges, number of internal nodes = depth (if we count root as depth 1). Typically, Huffman cost is sum leaf * path length in edges (depth-1). But constant shift: sum leaf * depth = sum leaf * (path_edges + 1) = sum leaf * path_edges + total_sum. Since total_sum is constant for all trees, minimizing sum leaf * path_edges is equivalent to minimizing sum leaf * depth. Actually sum leaf * depth = sum leaf * (path_edges+1) = sum leaf * path_edges + sum leaf. Since sum leaf is constant, minimizing sum leaf * depth is equivalent to minimizing sum leaf * path_edges. So Huffman's minimization of weighted path length (edges) corresponds to minimizing sum leaf * depth as well (up to constant). So Huffman gives the minimum total cost. Conversely, to maximize total cost, we want to maximize sum leaf * depth. This is known as the opposite: combine largest first yields maximum. A formal proof: In any tree, swapping two leaf weights such that the heavier leaf is placed in a position with larger depth will increase total cost. The greedy algorithm that repeatedly merges two largest is known to maximize sum of depths weighted by leaf values. This can be proved by exchange argument similar to Huffman.

    Thus solution: For each test case, sort descending and simulate using a max-heap or two queues.

    Given constraints up to 5e6 total N, sorting all test cases might be okay: total O( sum N log N ) with sorting, plus O(N) simulation. However, using a priority queue might be simpler but could be slower due to O(N log N) with larger constant. Using two queues after sorting is linear in merges.

    Let's think about two queues method: We want to always pick the two largest numbers among the remaining numbers (original and generated sums). We can sort the initial array in descending order. Then we maintain two queues: one for the original numbers (sorted descending) and one for the generated sums (which will be processed in increasing order? Actually the generated sums are produced by summing two largest numbers; these sums will be in non-increasing order? Let's check: If we always merge two largest, the generated sums will be decreasing? Example: numbers: 9,8,4,3,2. Merge 9+8=17, then next largest numbers: 7? Actually after first merge we have 17,4,3,2. 17 is largest, then we merge 17+4=21, which is larger than 17. So generated sums can increase. Wait: After merging two largest numbers, the sum is larger than at least one of them? Actually if we merge two largest, the sum is larger than both. So the generated sum is even larger than the largest original? Actually if we have numbers a1 >= a2 >= ... >= aN, then merging a1 and a2 gives s = a1 + a2, which is >= a1 + a2 > a1 (since a2 positive). So s > a1. So the generated sum is larger than the current maximum. So the new sum becomes the new maximum. Then next step we will take this maximum (s) and merge with the next largest remaining original number (a3). That sum s2 = s + a3 > s. So generated sums are strictly increasing if we keep merging with original numbers. However, after we exhaust original numbers, we might start merging sums together? Actually process: we start with sorted descending list. We'll always have the largest number being a sum that accumulates more and more. The second largest may be either a sum (if there are multiple sums) or an original number. But because sums are increasing, they will be the largest, and the second largest will be the next largest among the remaining original numbers (since all sums are larger than all original numbers? Not exactly: Suppose numbers: 100, 1,1,1,... many. After first merge: 100+1=101, then second largest is 1 (original). So sums are larger than any original. So the process always merges the current cumulative sum (which is the largest) with the next largest original number, until all original numbers are exhausted. Actually if there are multiple original numbers of equal value, we still merge cumulative sum with the next largest original. So essentially we are adding numbers one by one in descending order to a running total? Let's simulate: Start with sorted descending: a1 >= a2 >= ... >= aN. Merge a1 and a2 -> sum s1 = a1 + a2. Cost += s1. Now we have numbers: s1, a3, a4, ..., aN. Since s1 > a1 >= a3, s1 is largest. Merge s1 and a3 -> s2 = s1 + a3. Cost += s2. Continue: at step i (starting from 1), we have cumulative sum S_i = a1 + a2 + ... + a_{i+1}? Actually after k merges (k from 1 to N-1), we have merged first k+1 numbers? Let's see: after first merge, we used a1,a2 -> S1 = a1+a2. After second merge, we used S1 and a3 -> S2 = a1+a2+a3. After third merge, we use S2 and a4 -> S3 = a1+...+a4. So after k merges (k from 1 to N-1), we have cumulative sum T_k = sum_{i=1}^{k+1} a_i. Then the next merge (if k < N-1) will merge T_k and a_{k+2} to get T_{k+1} = T_k + a_{k+2}, costing T_{k+1}. So essentially the process is: start with largest number a1, then repeatedly add the next largest number to the cumulative sum, and each addition (i.e., merging) adds the new cumulative sum to total cost. This yields total cost = sum_{j=2}^{N} (sum of first j numbers). Because after we have cumulative sum of first j-1 numbers, we merge with a_j, cost = sum_{i=1}^{j} a_i. So total cost = sum_{j=2}^{N} prefix_sum_j. That is for the case where we always merge the current cumulative sum with the next largest original number. But is this always the case? This holds if we always pick the two largest and the largest is always the cumulative sum and the second largest is the next largest original number. But is it possible that at some point the second largest could be another generated sum rather than an original? For that to happen, we would need to have two generated sums simultaneously, meaning we didn't merge the cumulative sum with an original number but instead we created two separate sums. However, the greedy algorithm of repeatedly merging two largest will always result in this sequential pattern? Let's test with numbers where there are many large numbers, maybe the two largest are both original numbers initially. After first merge, we have one sum (a1+a2) and the rest original numbers. Now, is the second largest always the largest original among remaining? Yes, because the sum is > a1 (since a2 > 0), so sum is larger than any original (since a1 is the largest original, and sum > a1). So sum is the largest, the second largest is the next original (a3). So we merge sum and a3. After that, we get a larger sum (a1+a2+a3) which is even larger than previous sum. So it's always the largest, and the second largest is the next original a4 (since all other numbers are original or possibly previous sums? But after each merge, we only have one sum (the cumulative sum) and the remaining original numbers. Because each merge consumes the cumulative sum and one original to produce a new cumulative sum. So we never have two sums at the same time. So indeed the process is simply: sort descending, then cumulative sum, and total cost = sum_{j=2}^{N} prefix_sum_j, where prefix_sum_j is sum of largest j numbers? But careful: The ordering of merges we described corresponds to merging in descending order: first combine two largest originals, then combine resulting sum with next largest, etc. But is there any alternative order that might yield higher total cost? We argued that greedy merging largest first yields maximum. And that greedy leads to this sequential pattern. So indeed the maximum total cost is achieved by sorting descending and then summing the cumulative sums starting from sum of first two up to total sum.

    But we need to be certain that merging the two largest at each step always results in this pattern of having a single cumulative sum and the rest originals. That's true because after each merge, the sum becomes larger than any original remaining (since all originals are positive). Thus the largest number will always be the cumulative sum, and the second largest will be the largest remaining original. So the process is forced: after first merge, you have one sum (of the two largest), and the rest are originals. Then you always merge the sum (largest) with the largest remaining original. So the order is uniquely determined by sorting descending. Thus the total cost is simply sum of all prefix sums (excluding the first element alone). More precisely, let the numbers be sorted in non-increasing order: b1 >= b2 >= ... >= bN. Then total cost = b1+b2 (merge1) + (b1+b2+b3) (merge2) + (b1+b2+b3+b4) + ... + (b1+...+bN) (last merge). That equals sum_{k=2}^{N} (sum_{i=1}^{k} b_i).

    Thus we can compute total cost in O(N log N) by sorting descending and then computing prefix sums. Since N can be 1e6 per test, and total N across tests is 5e6, sorting each test individually is O(N log N). This should be fine in C++ with std::sort.

    But wait: The numbers are positive integers. Sorting descending and computing prefix sums yields total cost. This is simpler and more efficient than priority queue simulation. However, we must confirm that the greedy of always merging two largest indeed yields maximum total. I'm convinced. But let's test on a few more cases to ensure no counterexample. Consider numbers: 5,4,3,2. Descending sort: 5,4,3,2. According to formula: total = (5+4)=9, then 5+4+3=12, then 5+4+3+2=14 => total = 9+12+14 = 35. Simulate: merge 5+4=9, left: 9,3,2; merge 9+3=12, left: 12,2; merge 12+2=14 => total 35. Could there be a different merge order giving higher? Let's try alternative: merge 3+2=5 cost5, left: 5,4,5? Actually numbers:5,4,3,2. If we merge 3+2=5: cost5, left:5,4,5 (two 5's and 4). Then merge two largest: 5 and 5 ->10 cost10, left:10,4. Then merge 10+4=14 cost14 total =5+10+14=29 <35. Another: merge 5+2=7 cost7, left:7,4,3; merge 7+4=11 cost11, left:11,3; merge 11+3=14 cost14 total=7+11+14=32 <35. Another: merge 4+3=7 cost7, left:5,7,2; merge 7+5=12 cost12, left:12,2; merge 12+2=14 cost14 total=7+12+14=33 <35. So indeed 35 is max.

    What about numbers like 10,1,1,1? Sorting descending:10,1,1,1. total = (10+1)=11, then 12, then 13 => total =11+12+13=36. Alternative: merge three 1's first? Merge 1+1=2 cost2, left:10,2,1; merge 2+1=3 cost3? Actually careful: If we merge 1+1=2, cost2; left:10,2,1. Then we could merge 2+1=3 cost3, left:10,3; then 10+3=13 cost13 total=2+3+13=18? That's much smaller. Or merge 10+1=11 cost11, left:11,1,1; merge 1+1=2 cost2, left:11,2; merge 11+2=13 cost13 total=11+2+13=26. So 36 is max. So consistent.

    Thus maximum total cost = sum_{i=2}^{N} (prefix sum of i largest numbers). Equivalent to: let total_sum = S = sum of all numbers. Then prefix sums: P1 = a1, P2 = a1+a2,... PN=S. Total cost = P2+P3+...+PN = (S + (S - a1) + (S - a1 - a2) + ... + a_N?) Not exactly. But easier: sort descending, compute prefix sums, accumulate from index 2 to N.

    We need to confirm that this formula holds for any order? Actually we derived it under the assumption that we always merge the two largest, and that process leads to this cumulative pattern. But is it always optimal? Yes, because it's the greedy solution for maximization. However, we might want to double-check with scenario where there are equal numbers. It still holds.

    So algorithm: For each test case:

    • Read N and array A.
    • Sort A in descending order (or ascending and then iterate from back).
    • Compute prefix sum as we go: let sum = 0, total_cost = 0.
    • For i from 0 to N-1 (0-indexed): sum += A[i]; if i >= 1: total_cost += sum; // because after we have at least two numbers, the sum of first i+1 numbers corresponds to a merge cost.
    • Output total_cost.

    But careful: The merge process yields N-1 merges, and the costs are exactly the prefix sums from the sum of first two up to sum of all. So this matches.

    Thus we have an O(N log N) solution per test, dominated by sorting.

    But is there any nuance? Could there be a scenario where merging two largest does not produce a single cumulative sum? As argued, after first merge, the sum is larger than any original, so it's the unique maximum. The second largest is the largest remaining original. So indeed it's forced. So the process is essentially adding numbers to cumulative sum in descending order.

    Now check with sample: 4 2 1 3 sorted descending: 4,3,2,1. prefix sums: i=0 sum=4 (not added), i=1 sum=7 -> total=7, i=2 sum=9 -> total=16, i=3 sum=10 -> total=26. matches.

    Second sample: 9,8,4,3,2. prefix: sum=9, then sum=17 -> total=17, sum=21 -> total=38, sum=24 -> total=62, sum=26 -> total=88. matches.

    Thus solution is simple.

    Now consider edge cases: N=1? Then no operations needed, total time = 0. But constraints say N≥1. But is it possible that we need to output 0 for N=1? The process: only one number left, no summing needed, so time=0. Should handle. In our loop, we add only when i>=1, so for N=1, total stays 0. Good.

    Now need to handle large sums: total cost may be up to about N * S where S is sum of numbers, but actually it's sum of prefix sums, which for all numbers equal to M and N large is M * (sum_{j=2}^{N} j) = M * (N(N+1)/2 - 1). That's M * (N^2/2). For N=1e6, M=1e7, that's 1e7 * (1e12/2) = 5e18? Let's compute precisely: N=1e6, sum_{j=2}^{N} j = (N(N+1)/2 - 1) ≈ (1e61,000,001/2 -1) = (1e12/2? Actually 1e61,000,001 = 1,000,001,000,000 ≈ 1e12. Divide by 2 = 5e11. So product with M=1e7 yields 5e18. 5e18 fits within 64-bit signed? 2^63-1 = 9.22e18, so it fits. But we must ensure no overflow during accumulation. Use unsigned long long or long long. long long max is 9.22e18, so 5e18 is safe. However, if numbers are not all equal, the sum could be larger? Let's check extreme: all numbers 1e7, N=1e6 => total = 1e7 * (N(N+1)/2 - 1). N(N+1)/2 ≈ 5e11, product 5e18. But if numbers vary, the sum of all numbers S = 1e7 * 1e6 = 1e13. The sum of prefix sums is sum_{i=1}^{N} (N-i+1)a_i? Let's derive formula: total = sum_{k=2}^{N} (sum_{i=1}^{k} a_i) = a1(N-1) + a2*(N-2) + ... + a_{N-1}1 + a_N0? Actually check: a1 appears in P2, P3, ..., PN => (N-1) times. a2 appears in P2? P2 includes a1 and a2, a3 includes a1,a2,a3,... So a2 appears in P2, P3,..., PN => (N-2) times? Wait: Let's compute contributions: For sorted descending a1≥a2≥...≥aN. P2 = a1+a2; P3 = a1+a2+a3; ... PN = a1+...+aN. So total = (N-1)a1 + (N-2)a2 + (N-3)a3 + ... + 1a_{N-1} + 0a_N. Indeed a_N appears only in PN? Actually PN includes all, so a_N appears once? Let's check: a_N is in PN, but not in P2..P_{N-1}. So a_N appears 1 time, not 0. Because PN includes a_N. In our total we sum P2 through PN inclusive. So a_N appears in exactly one sum: PN. So contribution of a_i: For i=1: appears in P2, P3, ..., PN => N-1 times? Actually P2 includes a1, P3 includes a1,... PN includes a1, so that's (N-1) times? Count: from k=2 to N inclusive, number of terms = N-1. So a1 appears in all N-1 sums => contribution = a1 * (N-1). For i=2: appears in P2? Yes (since P2 includes a2), P3 includes a2,..., PN includes a2 => that's from k=2 to N => N-1 sums? Actually careful: P2 includes a2, so i=2 appears in sums for k>=2. Since k runs from 2 to N, a2 appears in all those sums? For k=2, a2 is included. For k=3, also included. Up to k=N, included. So a2 also appears in N-1 sums? That would mean all a_i appear in N-1 sums? That can't be because then total would be (N-1)S, but we know total is less than that. Let's recalc: P2 = a1+a2. P3 = a1+a2+a3. P4 = a1+a2+a3+a4, etc. So for a2: does it appear in P2? Yes. In P3? Yes. In P4? Yes. Up to PN? Yes. So a2 appears in all sums from P2 to PN, which is N-1 sums. Similarly a3 appears from P3 to PN: that's N-2 sums? Because P2 does not include a3. So a3 appears in sums for k>=3: from P3 to PN inclusive, count = N-2. a4 appears from P4 to PN: count = N-3. And a_N appears only in PN: count = 1. So contributions: a1: N-1, a2: N-1? Wait a2 appears in P2, P3,..., PN: that's (N-1) sums? But P2 includes a2, P3 includes a2,... PN includes a2 => that's N-1 sums if we count from 2 to N inclusive, that's N-1 sums. So indeed a2 appears in N-1 sums? But then total would be (N-1)(a1+a2) plus others? Let's test with N=4: a1,a2,a3,a4. Sum P2+P3+P4 = (a1+a2)+(a1+a2+a3)+(a1+a2+a3+a4) = 3a1 + 3a2 + 2a3 + 1a4. So contributions: a1:3, a2:3, a3:2, a4:1. So a2 appears 3 times (N-1=3). So yes a2 also appears N-1 times. For N=4, N-1=3. So a1 and a2 both appear 3 times. So in general, for sorted descending, a1 and a2 both appear N-1 times? But earlier I thought a2 would appear N-2 times; that was mistaken. Let's derive general formula: For i from 1 to N, a_i appears in sums P_k for k >= max(2,i). Because P_k includes a_i if k >= i (since P_k includes first k elements). But also P_k starts at k=2. So for i=1, appears for k=2..N => N-1 times. For i=2, appears for k=2..N => N-1 times (since k starts at 2). For i=3, appears for k=3..N => N-2 times. For i=4, appears for k=4..N => N-3 times. ... For i=N, appears for k=N..N => 1 time. So contributions: a1: N-1, a2: N-1, a3: N-2, a4: N-3, ..., aN: 1. So total cost = (N-1)(a1+a2) + (N-2)*a3 + (N-3)a4 + ... + 1aN.

    Thus maximum total cost is achieved by sorting descending: because we want larger coefficients to be paired with larger a_i. Since coefficients are (N-1) for two largest, then (N-2), (N-3),...,1. So to maximize sum, assign largest values to largest coefficients. Since coefficients are not sorted strictly decreasing? They are: c1=N-1, c2=N-1, c3=N-2, ..., cN=1. This sequence is non-increasing? For N>2, N-1 >= N-2 >= ... >= 1. But note c1=c2 are equal, both largest. So optimal assignment is to put two largest numbers to coefficients N-1 and N-1, the next largest to coefficient N-2, etc. That's exactly the sorted descending order. So the greedy merging largest first corresponds to this assignment.

    Thus we can compute total cost as sum_{i=1}^{N} coeff_i * a_i, with coefficients as above. But it's easier to compute via prefix sums.

    Now, we need to implement with large N. Sorting descending and accumulating prefix sums works fine.

    Complexities: sum of N across test cases ≤5e6, so sorting each test case individually: total O( sum N log N_i ) but each N_i could be up to 1e6, but total across tests 5e6, so sorting all numbers overall about 5e6 log(1e6) at worst if one test is huge? But we can sort each test independently, so total sorting cost sum(N_i log N_i). Since log N_i ≤ log 1e6 ≈ 20, and sum N_i =5e6, total operations ~ 100 million comparisons, which is fine in C++.

    Alternative: Use counting sort? But Ai up to 1e7, N up to 1e6, range is large, not feasible.

    Thus algorithm:

    • Read T.
    • For each test:
      • Read N.
      • Read N integers into vector.
      • Sort vector in descending order.
      • Initialize sum=0, total=0.
      • For i from 0 to N-1: sum += vec[i]; if (i >= 1) total += sum;
      • Print total.

    Edge Cases: N=1 -> total=0.

    Potential pitfalls: Input size large, need fast I/O. Use scanf/printf or ios_base sync.

    Now we must output for each test case.

    Double-check with small examples: N=2: numbers a,b. Sorted descending (say a>=b). total: i=0 sum=a (no add), i=1 sum=a+b, total+=a+b => total = a+b, correct. N=3: numbers a,b,c sorted descending a>=b>=c. total: sum after i0 = a; i1 sum=a+b total+=a+b; i2 sum=a+b+c total+=a+b+c => total = (a+b)+(a+b+c)=2a+2b+c, which matches our earlier formula for merging largest two first (2a+2b+c). Good.

    Thus solution.

    Now about proving greedy is optimal: we can refer to coefficient argument.

    Thus we can implement.

    One nuance: The problem states that Pandey will maximize the amount of time taken. We assume that he can choose order arbitrarily to maximize time. Greedy merging largest first yields maximum. So answer is as above.

    Now, consider that numbers are not necessarily sorted descending when given; we sort.

    Complexities: O(N log N) per test.

    Now, we must be careful about using 64-bit integers. Use long long (64-bit). Total cost can be up to ~5e18, fits in signed 64-bit. But for safety, use unsigned long long or long long.

    We'll compute prefix sum as we go.

    Implementation details in C++:

    #include <bits/stdc++.h> using namespace std;

    int main() { ios_base::sync_with_stdio(false); cin.tie(0); int T; cin >> T; while (T--) { int N; cin >> N; vector arr(N); for (int i=0; i<N; ++i) cin >> arr[i]; sort(arr.begin(), arr.end(), greater()); long long sum = 0; long long total = 0; for (int i=0; i<N; ++i) { sum += arr[i]; if (i >= 1) total += sum; } cout << total << '\n'; } return 0; }

    But careful: Input might be up to 5e6 numbers, so using vector per test case with dynamic allocation is fine, but we should ensure we free memory after each test, or reuse vector? We can just create vector each time, it will be deallocated after loop. But large allocations might cause overhead; we can use vector and call shrink_to_fit or just rely on moving out of scope.

    Alternatively, we can read numbers into an array and sort using std::sort.

    We need to handle large input; use scanf for faster reading? cin with sync turned off is usually fast enough for 5e6 integers. But to be safe, use scanf.

    Implementation with scanf:

    int main() { int T; scanf("%d", &T); while (T--) { int N; scanf("%d", &N); vector arr(N); for (int i=0; i<N; ++i) scanf("%d", &arr[i]); sort(arr.begin(), arr.end(), greater()); long long sum = 0, ans = 0; for (int i=0; i<N; ++i) { sum += arr[i]; if (i) ans += sum; } printf("%lld\n", ans); } return 0; }

    But note: using greater() sorts descending; we can also sort ascending and iterate from end.

    Time complexity: Sorting each test case O(N log N). With total N 5e6, it's fine.

    But can we do it without sorting? Since we need to assign numbers to coefficients that are (N-1) for the two largest, (N-2) for next, etc. So we need to sort descending. So yes.

    But maybe there is even more efficient: we can use nth_element or partial sort to get largest numbers? But we need all numbers sorted to assign coefficients? Actually coefficients are decreasing but only two coefficients are equal. However, we still need to know order to assign the largest two to highest coefficient, next largest to next, etc. That's sorting.

    Given constraints, it's fine.

    However, note: sum of N across test cases is up to 5e6, but T can be up to 100. Sorting each test case individually is fine.

    Now, we should confirm that the greedy of merging largest first indeed gives the maximum total time, and there is no other sequence that yields higher. Let's think of a potential counterexample: maybe merging three numbers first? But we always merge two. Could there be a tree shape that is not a simple chain? The greedy we described yields a "right-skewed" tree? Actually the tree is a "left-deep" tree: one branch is a chain merging all numbers sequentially, the other branch is the next number. But because we always merge the cumulative sum with the next largest, the tree shape is like a right-leaning? Let's consider tree: leaves: a1, a2, a3, a4. Process: first merge a1 and a2 => internal node I1 = a1+a2. Then merge I1 and a3 => I2 = a1+a2+a3. Then merge I2 and a4 => root = a1+a2+a3+a4. So the tree is a degenerate binary tree where each internal node's left child is the previous cumulative sum and right child is next leaf. This is essentially a "comb" tree.

    But are there other trees that could yield higher total? For weighted depth maximization, we want the larger weights to have larger depth. In a full binary tree with N leaves, the maximum possible sum of leaf* depth is achieved by making the tree as unbalanced as possible (i.e., a degenerate tree) and assigning the largest weights to the deepest leaves. Since we have control over both shape and assignment, the maximum sum is achieved by a "chain" shape where leaves are added one by one to a cumulative sum, and the largest leaf values are placed deepest. However, is there any shape that yields even higher than a chain? Suppose we have N=4. The chain shape (skewed) gives depths: two leaves at depth 3 (if we count internal nodes) and one at depth 2, one at depth 1? Let's compute: In the chain described above, leaves: a1 and a2 are merged first, then with a3, then with a4. The depths (number of internal nodes on path): for a1 and a2, depth = 3 (they are ancestors of three internal nodes: I1, I2, root). For a3, depth = 2 (I2 and root). For a4, depth = 1 (root only). So coefficients: a1,a2:3, a3:2, a4:1. That's exactly our coefficient assignment: (N-1)=3 for two largest, (N-2)=2, (N-3)=1? Actually N-3=1 for a4. So indeed chain gives coefficients: two leaves have depth N-1? For N=4, max depth = 3 = N-1. So the deepest leaves get depth N-1, which is maximum possible depth for any leaf in a binary tree with N leaves? In a full binary tree with N leaves, the maximum depth of a leaf is N-1 (if the tree is completely skewed). So to maximize total weighted depth, we want the largest weights at the deepest positions. So we want a tree where there are leaves with depths ranging from 1 to N-1, with exactly two leaves at depth N-1? Actually in a full binary tree with N leaves, the sum of depths over all leaves is something? But we can consider: The number of leaves with depth N-1? In a skewed tree (like a right spine), the shape: leaf a1 and a2 are deepest? Let's draw: root merges (subtree, leaf). The subtree itself merges (subtree, leaf) recursively. At each internal node, one child is a leaf, the other is a subtree. In such a tree, the leaves depths: the leaf that is merged last (a4) has depth 1 (just root). The leaf merged before that (a3) depth 2, and the two leaves from the initial merge have depth 3. So we have one leaf at depth 1, one at depth 2, two at depth 3. In general, for N leaves, the skewed tree yields depths: one leaf at depth 1, one at depth 2, one at depth 3, ..., and two leaves at depth N-1? Let's derive: For N leaves, the tree built by repeatedly merging the cumulative sum with a new leaf yields depths: the last leaf (merged at final step) has depth 1, the second last has depth 2, ..., the third leaf (i.e., after the initial two) has depth N-2? Wait we need to compute properly.

    Let's define the process: start with two leaves merged to form internal node I1. Then we merge I1 with leaf3 to form I2, then I2 with leaf4 to form I3, ... until we merge I_{N-2} with leafN to form root. So leafN is merged last: its depth = 1 (only root). leaf(N-1) is merged at penultimate step: its depth = 2 (it is child of I_{N-2} and also root? Actually leaf(N-1) is merged with I_{N-3}? Let's index: For N leaves, we have leaves L1..LN. The tree: root = merge(I_{N-2}, LN). I_{N-2} = merge(I_{N-3}, L_{N-1}). And so on, until I1 = merge(L1, L2). So depths: L1 and L2 are in the deepest subtree: they are leaves under I1, which is under I2, ... up to root. So depth(L1) = N-1 (since there are N-1 internal nodes: I1, I2, ..., I_{N-2}, root? Actually count internal nodes: total N-1. L1 is under I1 (depth count starts at 1 for root? If root is internal node at top, then depth count = number of internal nodes on path from leaf to root. For L1: path: I1, I2, ..., I_{N-2}, root => that's (N-2) +1 = N-1? Let's count: internal nodes: I1, I2, ..., I_{N-2} are N-2 internal nodes? Actually number of merges = N-1. The internal nodes correspond to merges: first merge yields I1, second yields I2, ..., (N-2)th merge yields I_{N-2}, final merge yields root. So total internal nodes = N-1. L1 is under I1, I2, ..., I_{N-2}, root => that's (N-2) +1 = N-1? I'm mixing. Let's index properly: For N=4, internal nodes: I1 (merge L1,L2), I2 (merge I1,L3), root (merge I2,L4). So internal nodes count: I1, I2, root = 3 = N-1. Depth(L1) counts internal nodes on path: includes I1, I2, root => 3 = N-1. Depth(L2) same. Depth(L3): path: I2, root => 2 = N-2? Actually N-2=2. Depth(L4): root =>1 = N-3? N-3=1. So pattern: For N leaves, depths: two leaves at depth N-1? For N=4, two at depth 3, one at depth 2, one at depth 1. For N=5, we would have: L1,L2 depth 4, L3 depth 3, L4 depth 2, L5 depth 1. So indeed two leaves at depth N-1, one at N-2, one at N-3, ..., one at 1. That yields coefficients: depth counts: two leaves get depth N-1, one leaf gets depth N-2, ..., one leaf gets depth 1. That matches our coefficient distribution: c1=N-1, c2=N-1, c3=N-2, ..., cN=1. So indeed the chain tree is the shape that yields maximum sum when numbers are sorted descending.

    Could there be a tree with different shape that yields even higher sum? For maximizing weighted sum with positive weights, we want as much weight as possible at deepest leaves. However, the depth of a leaf is limited by N-1. To have two leaves at depth N-1, we need the tree to be completely skewed (i.e., a chain) because any full binary tree with N leaves has at most two leaves at maximum depth? Actually consider a full binary tree: maximum depth possible is N-1 (a degenerate tree). In such a tree, there is exactly one leaf at depth 1, one at depth 2, ..., and two at depth N-1? Let's think: In a degenerate tree where each internal node has one leaf and one subtree, the leaf depths follow that pattern. That seems to give the maximum possible depth sum? But could we have more than two leaves at maximum depth? The maximum depth for any leaf is N-1, but can we have three leaves at depth N-1? In a full binary tree with N leaves, the sum of depths is fixed? Actually the sum of depths is not fixed; different trees yield different depth distributions. For a given N, the maximum possible sum of depths (unweighted) is achieved by the most unbalanced tree? Let's compute sum of depths (counting internal nodes) for a full binary tree with N leaves. In an unbalanced tree, depths can be as high as N-1 for some leaves, but there will be many leaves with small depths. For a completely right-skewed tree (like a vine), we have depths: 1,2,3,..., N-2, N-1, N-1 (two leaves at max depth). Sum of depths = 1+2+3+...+(N-2) + (N-1)+(N-1) = (N-2)(N-1)/2 + 2(N-1) = (N-1)(N-2+4)/2? Let's compute: sum_{i=1}^{N-2} i = (N-2)(N-1)/2. Add 2(N-1) gives (N-2)(N-1)/2 + 2(N-1) = (N-1)( (N-2)/2 + 2 ) = (N-1)( (N-2+4)/2 ) = (N-1)(N+2)/2. So sum depths = (N-1)(N+2)/2. For N=4, sum depths = 3*6/2=9, which matches: 1+2+3+3=9.

    If we consider a balanced tree, sum depths would be lower. So to maximize weighted sum, we want deepest depths assigned to largest weights, so the shape that yields the highest depth sum for a given N is the one that maximizes the sum of depths. The maximum sum of depths for a full binary tree with N leaves is achieved by the most unbalanced tree. Because deeper leaves increase sum. The most unbalanced tree is exactly the chain (or left-deep) tree. Does any tree yield even larger sum of depths? Possibly a tree where all leaves have depth N-1 is impossible because a full binary tree with N leaves must have internal nodes count N-1, and the height cannot exceed N-1. To have all leaves depth N-1, the tree would need to be a perfect tree of height N-1, but that would have many leaves (2^{N-1}) which is far larger than N for N>2. So not possible. The chain gives the maximum sum of depths.

    Therefore, the maximum total weighted depth is achieved by using the most unbalanced tree (chain) and assigning the largest weights to the deepest leaves. That's exactly the greedy merging largest first, which produces the chain tree with descending order assignment.

    Thus our approach is correct.

    Now, we can compute answer simply as sum of prefix sums.

    But there is nuance: The problem says Pandey can choose two numbers and replace them with their sum, and he will do it in the worst possible way. This implies he will maximize total time. The worst possible way is to combine numbers in the order that yields maximum total time, which is as we described. So we output that maximum.

    Thus final solution.

    Now, we should implement with care for large input. Use scanf/printf, or fast cin.

    Complexities: Sorting O(N log N). With total N up to 5e6, it should pass.

    But we can also compute using partial sums after sorting.

    Implementation details:

    We need to handle up to 10^2 test cases, sum of N 5e6, memory for vector of size up to 1e6. That's okay: vector of ints of size 1e6 uses ~4 MB. For multiple test cases sequentially, it's fine.

    Now we produce the answer.

    But wait, are we certain that the greedy merging largest first yields maximum? Let's double-check with small N=4 with distinct numbers: 10,9,8,7. Sorted descending: 10,9,8,7. Prefix sums: after 10:10; after 9:19 -> add 19; after 8:27 -> add 27; after 7:34 -> add 34; total=19+27+34=80. Alternative order: maybe merge 8+7=15, then merge 10+9=19, then merge 19+15=34 total=15+19+34=68. Another: merge 10+7=17, then 9+8=17, then 17+17=34 total=17+17+34=68. Another: merge 10+8=18, then 9+7=16, then 18+16=34 total=18+16+34=68. Another: merge 9+7=16, then 10+16=26, then 26+8=34 total=16+26+34=76. Another: merge 10+8=18, then 18+7=25, then 25+9=34 total=18+25+34=77. So 80 seems max. So our method yields 80.

    Now test with all equal: 1,1,1,1: sorted descending same. Prefix sums: after 1:1; after second:2 -> add2; third:3 -> add3; fourth:4 -> add4 total=9. Other order? Merge 1+1=2, then 2+1=3, then 3+1=4 total=2+3+4=9. Any other? Merge 1+1=2, then 1+1=2, then 2+2=4 total=2+2+4=8. So max is 9.

    Thus formula holds.

    Now confirm N=5 with numbers 5,4,3,2,1: Prefix sums: after 5:5; after 4:9->+9=9; after 3:12->+12=21; after 2:14->+14=35; after 1:15->+15=50 total=9+12+14+15=50? Wait sum: 9+