output_description: Print the answer.
  
  * * *
input_description: The input is given from Standard Input in the following format:
  
      
      
      N M
attempt: from functools import cmp_to_key
       
  n = int(input())
  a = list(map(int, input().split()))
       
  def group(a):
  	d = {}
      for i, x in enumerate(a):
        d.setdefault(x, []).append(i)
        s = sorted(d.items(), key=cmp_to_key(lambda x, y: x[0] - y[0]),
                 reverse=True)
        return list(map(lambda x: [x[0], x[1][0], len(x[1])], s))
       
  ans = [0] * n
  g = group(a)
  g.append([0, 0, 0])
  for c, n in zip(g[:-1], g[1:]):
    ans[c[1]] += (c[0] - n[0]) * c[2]
    n[1] = min(c[1], n[1])
    n[2] += c[2]
  
    [print(a) for a in ans]
problem_description: Statement
  
  Snuke loves puzzles.
  
  Today, he is working on a puzzle using `S`\- and `c`-shaped pieces. In this
  puzzle, you can combine two `c`-shaped pieces into one `S`-shaped piece, as
  shown in the figure below:
  
  ![9b0bd546db9f28b4093d417b8f274124.png](https://atcoder.jp/img/arc069/9b0bd546db9f28b4093d417b8f274124.png)
  
  Snuke decided to create as many `Scc` groups as possible by putting together
  one `S`-shaped piece and two `c`-shaped pieces.
  
  Find the maximum number of `Scc` groups that can be created when Snuke has N
  `S`-shaped pieces and M `c`-shaped pieces.
samples: [{"input": "1 6", "output": "2\n    \n\nTwo `Scc` groups can be created as follows:\n\n  * Combine two `c`-shaped pieces into one `S`-shaped piece\n  * Create two `Scc` groups, each from one `S`-shaped piece and two `c`-shaped pieces\n\n* * *"}, {"input": "12345 678901", "output": "175897"}]