output_description: Print the maximum total comfort the N players can get.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      A_1 A_2 \dots A_N
attempt: import os
  import sys
  from io import BytesIO, IOBase
  
  # from collections import defaultdict as dd
  # from collections import deque as dq
  # import itertools as it
  # from math import sqrt, log, log2
  # from fractions import Fraction
  import heapq
  
  
  def main():
      n = int(input())
      nums = list(map(int, input().split()))
      nums.sort(reverse=True)
      if n <= 3:
          print(sum(nums[:2]))
          exit()
  
      hp = list()
      ans = 0
      # Push the first three intervals
      heapq.heappush(hp, (-nums[1], nums[0]))
      heapq.heappush(hp, (-nums[2], nums[0]))
      heapq.heappush(hp, (-nums[2], nums[1]))
      ans = sum(nums[:2])
  
      i = 3
      while i < n:
          comfort, big = heapq.heappop(hp)
          ans += -comfort
  
          small = -comfort
  
          curr = nums[i]  # what enters the circle
  
          # push the smaller interval
          heapq.heappush(hp, (-curr, small))
          heapq.heappush(hp, (-curr, big))
          i += 1
      print(ans)
  
  
  # region fastio
  BUFSIZE = 8192
  
  
  class FastIO(IOBase):
      newlines = 0
  
      def __init__(self, file):
          self._fd = file.fileno()
          self.buffer = BytesIO()
          self.writable = "x" in file.mode or "r" not in file.mode
          self.write = self.buffer.write if self.writable else None
  
      def read(self):
          while True:
              b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
              if not b:
                  break
              ptr = self.buffer.tell()
              self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
          self.newlines = 0
          return self.buffer.read()
  
      def readline(self):
          while self.newlines == 0:
              b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
              self.newlines = b.count(b"\n") + (not b)
              ptr = self.buffer.tell()
              self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
          self.newlines -= 1
          return self.buffer.readline()
  
      def flush(self):
          if self.writable:
              os.write(self._fd, self.buffer.getvalue())
              self.buffer.truncate(0), self.buffer.seek(0)
  
  
  class IOWrapper(IOBase):
      def __init__(self, file):
          self.buffer = FastIO(file)
          self.flush = self.buffer.flush
          self.writable = self.buffer.writable
          self.write = lambda s: self.buffer.write(s.encode("ascii"))
          self.read = lambda: self.buffer.read().decode("ascii")
          self.readline = lambda: self.buffer.readline().decode("ascii")
  
  
  sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
  input = lambda: sys.stdin.readline().rstrip("\r\n")
  # endregion
  
  if __name__ == "__main__":
      main()
  
problem_description: Statement
  
  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.
  
  The 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.
  
  When 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.
  
  What 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?
samples: [{"input": "4\n    2 2 1 3", "output": "7\n    \n\nBy arriving at the place in the order Player 4, 2, 1, 3, and cutting into the\ncircle as shown in the figure, they can get the total comfort of 7.\n\n![Figure](https://img.atcoder.jp/ghi/766a260a0019ea93e86e0588cc4db868.png)\n\nThey cannot get the total comfort greater than 7, so the answer is 7.\n\n* * *"}, {"input": "7\n    1 1 1 1 1 1 1", "output": "6"}]