I found an interesting problem on https://codeforces.com/problemset/problem/931/C:
Anya and Kirill are doing a physics laboratory work. In one of the tasks they have to measure some value n times, and then compute the average value to lower the error.

Kirill has already made his measurements, and has got the following integer values: x_1, x_2, ..., x_{n}. It is important that the values are close to each other, namely, the difference between the maximum value and the minimum value is at most 2.

Anya does not want to make the measurements, however, she can't just copy the values from Kirill's work, because the error of each measurement is a random value, and this coincidence will be noted by the teacher. Anya wants to write such integer values y_1, y_2, ..., y_{n} in her work, that the following conditions are met:  the average value of x_1, x_2, ..., x_{n} is equal to the average value of y_1, y_2, ..., y_{n}; all Anya's measurements are in the same bounds as all Kirill's measurements, that is, the maximum value among Anya's values is not greater than the maximum value among Kirill's values, and the minimum value among Anya's values is not less than the minimum value among Kirill's values; the number of equal measurements in Anya's work and Kirill's work is as small as possible among options with the previous conditions met. Formally, the teacher goes through all Anya's values one by one, if there is equal value in Kirill's work and it is not strike off yet, he strikes off this Anya's value and one of equal values in Kirill's work. The number of equal measurements is then the total number of strike off values in Anya's work. 

Help Anya to write such a set of measurements that the conditions above are met.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 100 000) — the numeber of measurements made by Kirill.

The second line contains a sequence of integers x_1, x_2, ..., x_{n} ( - 100 000 ≤ x_{i} ≤ 100 000) — the measurements made by Kirill. It is guaranteed that the difference between the maximum and minimum values among values x_1, x_2, ..., x_{n} does not exceed...

I tried it in Python, but could not do it. Can you solve it?
n=int(input())
x=input().split()
x=[int(k) for k in x]

rem=[]
x.sort()

mn = x[0]
mx = x[-1]

if (mx-mn<=1):
	print(len(x))
	for k in x:
		print(k, end=' ')
	print()
else:
	avg=mn+1
	expsum = avg*len(x)
	sm=0
	countmn=0
	countavg=0
	countmx=0
	for k in x:
		sm+=k
	if (sm-expsum)>0:
		rem=x[len(x)-(sm-expsum):len(x)]
		x=x[0:len(x)-(sm-expsum)]
	if (sm-expsum)<0:
		rem=x[0:(expsum-sm)]
		x=x[(expsum-sm):len(x)]
	if len(x)%2==1:
		rem.append(avg)
		for i in range(len(x)):
			if (x[i]==avg):
				x=x[0:i]+x[i+1:len(x)]
				break
	for k in x:
		if k==mn:
			countmn+=1
		if k==avg:
			countavg+=1
		if k==mx:
			countmx+=1
	if countmn+countmx<countavg:
		print(countmn+countmx+len(rem))
		for i in range(int(len(x)/2)):
			rem.append(mn)
			rem.append(mx)
	else:
		print(countavg+len(rem))
		for i in range(len(x)):
			rem.append(avg)
	for k in rem:
		print(k, end=' ')
	print()