output_description: Print the maximum possible sum of the absolute differences between the
  adjacent elements after arranging the given integers in a row in any order you
  like.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      A_1
      :
      A_N
attempt: import itertools
  import sys
  
  H, W = [int(i) for i in input().split(" ")]
  
  cross = [[0] * (H + W - 1) for _ in range(H + W - 1)]
  for i, line in enumerate(sys.stdin):
      for j, c in enumerate(line.strip()):
          if c == "#":
              cross[i + j][i - j + W - 1] = 1
  
  across = [[0] + list(itertools.accumulate(xs)) for xs in cross]
  r_cross = [[xs[i] for xs in cross] for i in range(H + W - 1)]
  across2 = [[0] + list(itertools.accumulate(xs)) for xs in r_cross]
  
  r = 0
  for i in range(H + W - 1):
      for j in range(H + W - 1):
          if cross[i][j] != 1:
              continue
          for k in range(j + 1, H + W - 1):
              if cross[i][k] == 1:
                  if i - (k - j) >= 0:
                      r += across[i - (k - j)][k + 1] - across[i - (k - j)][j]
                  if i + (k - j) < H + W - 1:
                      r += across[i + (k - j)][k + 1] - across[i + (k - j)][j]
  
  for i in range(H + W - 1):
      for j in range(H + W - 1):
          if cross[j][i] != 1:
              continue
          for k in range(j + 1, H + W - 1):
              if cross[k][i] == 1:
                  if i - (k - j) >= 0:
                      r += across2[i - (k - j)][k] - across2[i - (k - j)][j + 1]
                  if i + (k - j) < H + W - 1:
                      r += across2[i + (k - j)][k] - across2[i + (k - j)][j + 1]
  
  print(r)
  
problem_description: Statement
  
  You are given N integers; the i-th of them is A_i. Find the maximum possible
  sum of the absolute differences between the adjacent elements after arranging
  these integers in a row in any order you like.
samples: [{"input": "5\n    6\n    8\n    1\n    2\n    3", "output": "21\n    \n\nWhen the integers are arranged as 3,8,1,6,2, the sum of the absolute\ndifferences between the adjacent elements is |3 - 8| + |8 - 1| + |1 - 6| + |6\n- 2| = 21. This is the maximum possible sum.\n\n* * *"}, {"input": "6\n    3\n    1\n    4\n    1\n    5\n    9", "output": "25\n    \n\n* * *"}, {"input": "3\n    5\n    5\n    1", "output": "8"}]