output_description: Print the amount of change as an integer.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
attempt: N = int(input())
  A_list = list(map(int, input().split()))
  A_list.sort(reverse=True)
  indx_list = []
  for i in range(1, 100000, 2):
      indx_list.append(i)
  insx_list = []
  for j in range(0, 20):
      insx_list.extend(indx_list[: 2**j])
  mx_cmfrt = 0
  reached_list = [A_list[0], A_list[0]]
  for j in range(1, len(A_list)):
      cmfrt = min(reached_list[insx_list[j - 1] - 1], reached_list[insx_list[j - 1]])
      reached_list.insert(insx_list[j - 1], A_list[j])
      mx_cmfrt += cmfrt
  print(mx_cmfrt)
  
problem_description: Statement
  
  We will buy a product for N yen (the currency of Japan) at a shop.
  
  If we use only 1000-yen bills to pay the price, how much change will we
  receive?
  
  Assume we use the minimum number of bills required.
samples: [{"input": "1900", "output": "100\n    \n\nWe will use two 1000-yen bills to pay the price and receive 100 yen in change.\n\n* * *"}, {"input": "3000", "output": "0\n    \n\nWe can pay the exact price."}]