{"problem":{"name":"Chat in a Circle","description":{"content":"Quickly after finishing the tutorial of the online game _ATChat_, you have decided to visit a particular place with $N-1$ players who happen to be there. These $N$ players, including you, are numbered","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc173_d"},"statements":[{"statement_type":"Markdown","content":"Quickly after finishing the tutorial of the online game _ATChat_, you have decided to visit a particular place with $N-1$ players who happen to be there. These $N$ players, including you, are numbered $1$ through $N$, and the **friendliness** of Player $i$ is $A_i$.\nThe $N$ players will arrive at the place one by one in some order. To make sure nobody gets lost, you have set the following rule: players who have already arrived there should form a circle, and a player who has just arrived there should cut into the circle somewhere.\nWhen each player, except the first one to arrive, arrives at the place, the player gets **comfort** equal to the smaller of the friendliness of the clockwise adjacent player and that of the counter-clockwise adjacent player. The first player to arrive there gets the comfort of $0$.\nWhat is the maximum total comfort the $N$ players can get by optimally choosing the order of arrivals and the positions in the circle to cut into?\n\n## Constraints\n\n*   All values in input are integers.\n*   $2 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq A_i \\leq 10^9$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\dots$ $A_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc173_d","tags":[],"sample_group":[["4\n2 2 1 3","7\n\nBy arriving at the place in the order Player $4, 2, 1, 3$, and cutting into the circle as shown in the figure, they can get the total comfort of $7$.\n![image](https://img.atcoder.jp/ghi/766a260a0019ea93e86e0588cc4db868.png)\nThey cannot get the total comfort greater than $7$, so the answer is $7$."],["7\n1 1 1 1 1 1 1","6"]],"created_at":"2026-03-03 11:01:14"}}