The teacher gives a mental ability question to Raju. The question is as follows:-
Raju is in an elevator. Given by his teacher is an array of size N which denotes the number of floors and has a 1 based indexing. The elevator starts from the ground and moves up and down, X and Y floors respectively. There is a code used in the elevator according to which it moves up X floors given at odd indexes of the array and moves down Y floors given at even indexes of the array. He is asked to go to the highest floor possible. Help him to sort the array such that he reaches the highest floor after traversing the whole array from starting till the end, without skipping any index.
He always prefers to move more number of floors up and less number of floors down. Once he gets into the elevator, the elevator should not reach the ground again, if it does return -1.
Example 1:
Input : arr[ ] = {2, 3, 4, 5}
Output : 5 2 4 3
Explanation:
Array can be arranged as {5,3,4,2} or 
{4,3,5,2} or {4,2,5,3} but it will get 
arranged as {5,2,4,3} because he always 
prefer to move more number of floors up 
and less number of floors down.
Example 2:
Input : arr[ ] = {1, 1} 
Output :  Not Possible 
 
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function game_with_number() that takes sizeOfArray (n), an array (arr), and return the sorted array or if it is Not Possible return -1. The driver code takes care of the printing.
Expected Time Complexity: O(N*LOG(N)).
Expected Auxiliary Space: O(N).
 
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ arr[i] ≤ 10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Data structures

Starter code: #User function Template for python3



def reaching_height (n, arr) : 

    #Complete the function

    



Solutions:
def reaching_height(n, arr):
	arr.sort()
	lst = []
	if arr.count(arr[0]) == n and n > 1:
		return [-1]
	else:
		for i in range(0, n // 2):
			x = i + 1
			lst.extend([arr[-x], arr[i]])
		if n % 2 != 0:
			lst.append(arr[n // 2])
		return lst


def reaching_height(n, arr):
	arr.sort()
	r = []
	i = 0
	j = n - 1
	p = 0
	while i < j:
		r.append(arr[j])
		r.append(arr[i])
		p += arr[j]
		p -= arr[i]
		if p <= 0:
			return [-1]
		i += 1
		j -= 1
	if n % 2 == 1:
		r.append(arr[i])
	return r


def reaching_height(n, arr):
	arr.sort()
	ans = [0] * n
	(j, k) = (0, n - 1)
	for i in range(0, n, 2):
		ans[i] = arr[k]
		k -= 1
		if i + 1 == n:
			break
		ans[i + 1] = arr[j]
		j += 1
	return [-1] if n > 1 and arr.count(arr[0]) == n else ans


def reaching_height(n, a):
	a.sort()
	ans = []
	for i in range(n // 2):
		ans.append(a[n - 1 - i])
		ans.append(a[i])
	if n % 2 == 1:
		ans.append(a[n // 2])
	s = 0
	for i in range(n):
		if i % 2 == 0:
			s += ans[i]
		else:
			s -= ans[i]
		if s <= 0:
			return [-1]
	return ans


def reaching_height(n, arr):
	if len(set(arr)) == 1 and n != 1:
		return [-1]
	arr.sort()
	i = 0
	j = n - 1
	lis = []
	while i < j:
		lis.append(arr[j])
		lis.append(arr[i])
		i += 1
		j -= 1
	if n % 2 != 0:
		lis.append(arr[i])
	for i in range(n):
		arr[i] = lis[i]
	return arr


def reaching_height(n, arr):
	if n == 1:
		return arr
	arr.sort()
	i = 0
	j = n - 1
	result = [0 for i in range(n)]
	k = 0
	while i <= j:
		if k % 2 == 0:
			result[k] = arr[j]
			j -= 1
		else:
			result[k] = arr[i]
			i += 1
		k += 1
	if result[0] == result[-1]:
		return [-1]
	return result


def reaching_height(n, arr):
	arr.sort()
	list1 = []
	(i, j) = (0, n - 1)
	sum1 = 0
	k = 0
	while i <= j:
		if i == j:
			list1.append(arr[j])
			sum1 += arr[j]
			k += 1
		else:
			list1.append(arr[j])
			sum1 += arr[j]
			list1.append(arr[i])
			sum1 -= arr[i]
			if sum1 <= 0:
				return [-1]
		j -= 1
		i += 1
	if sum1 <= 0:
		return [-1]
	return list1


def reaching_height(n, arr):
	if n == 1:
		return arr
	arr.sort()
	brr = list(reversed(arr))
	output = []
	for i in range(n):
		output.append(brr[i])
		output.append(arr[i])
	return output[:n] if output[0] > output[1] else [-1]


def reaching_height(n, arr):
	if n == 1:
		return arr
	if arr.count(arr[0]) == n:
		return (-1,)
	k = []
	lis = arr.copy()
	lis.sort()
	j = n - 1
	for i in range(n):
		k.append(lis[j])
		k.append(lis[i])
		j -= 1
		if len(k) == n:
			break
	for i in range(n):
		arr[i] = k[i]
	return arr


def reaching_height(n, arr):
	arr.sort()
	arr2 = []
	i = -1
	for i in range(n // 2):
		arr2.append(arr[n - i - 1])
		arr2.append(arr[i])
	if n % 2 != 0:
		arr2.append(arr[i + 1])
	j = arr2[0]
	for i in range(1, n):
		if i % 2 != 0:
			j -= arr2[i]
			if j <= 0:
				return (-1,)
		else:
			j += arr2[i]
	return arr2


def reaching_height(n, arr):
	if n == 1:
		return arr
	if arr.count(arr[0]) == n:
		return (-1,)
	l = []
	x = arr.copy()
	x.sort()
	j = n - 1
	for i in range(n):
		l.append(x[j])
		l.append(x[i])
		j = j - 1
		if len(l) == n:
			break
	for i in range(n):
		arr[i] = l[i]
	return arr


def reaching_height(n, arr):
	if len(arr) == 1:
		return arr
	if arr.count(arr[0]) == n:
		return (-1,)
	arr.sort()
	mid = n // 2
	high = arr[mid:]
	high.reverse()
	low = arr[:mid]
	li = []
	k = 0
	f = 0
	for i in range(n):
		if i % 2 == 0:
			li.append(high[k])
			k += 1
		else:
			li.append(low[f])
			f += 1
	k = 0
	f = 0
	sum = 0
	for i in range(n):
		if i % 2 == 0:
			sum += high[k]
			k += 1
		else:
			sum -= low[f]
			f += 1
	return li if sum > 0 else (-1,)


def reaching_height(n, arr):
	if n == 1:
		return [arr[0]]
	arr.sort(reverse=True)
	ans = [0] * n
	(m, k) = (0, 0)
	j = n - 1
	for i in range(n):
		if i % 2 == 0:
			ans[k] = arr[m]
			m += 1
			k += 1
		else:
			ans[k] = arr[j]
			j -= 1
			k += 1
	if len(set(ans)) == 1:
		return [-1]
	return ans


def reaching_height(n, arr):
	if n == 1:
		return arr
	if arr.count(arr[0]) == n:
		return [-1]
	answer = []
	arr.sort()
	(front, rear) = (0, len(arr) - 1)
	while rear > front:
		answer.append(arr[rear])
		answer.append(arr[front])
		rear -= 1
		front += 1
		if rear == front:
			answer.append(arr[rear])
	if sum([answer[x] if x % 2 == 0 else -answer[x] for x in range(n)]) <= 0:
		return [-1]
	else:
		return answer


def reaching_height(n, arr):
	l = [0 for i in range(n)]
	arr.sort()
	a = 1
	if n % 2 == 0:
		b = n - 2
	else:
		b = n - 1
	s = 0
	for i in range(0, n):
		if i < int(n / 2):
			l[a] = arr[i]
			s = s - l[a]
			a = a + 2
		else:
			l[b] = arr[i]
			s = s + l[b]
			b = b - 2
	if len(set(l)) == 1 and len(l) != 1:
		return [-1]
	else:
		return l


from collections import deque

def reaching_height(n, arr):
	arr.sort()
	arr_odd = arr[n // 2:]
	arr_even = deque(arr[:n // 2])
	for i in range(1, len(arr) + 1):
		if i % 2 == 1:
			arr[i - 1] = arr_odd.pop()
		else:
			arr[i - 1] = arr_even.popleft()
	floor = 1
	for (index, item) in enumerate(arr):
		if index % 2 == 1:
			floor += item
		else:
			floor -= item
		if floor == 1:
			return [-1]
	return arr


def reaching_height(n, arr):
	if arr == [arr[0]] * n and n != 1:
		return [-1]
	arr.sort(reverse=True)
	(e, o) = (0, 0)
	if n % 2 == 0:
		odd = arr[:n // 2]
		even = arr[n // 2:]
		ans = []
		even.reverse()
		while e < n // 2:
			ans.append(odd[o])
			ans.append(even[e])
			e += 1
			o += 1
		return ans
	else:
		odd = arr[:n // 2 + 1]
		even = arr[n // 2 + 1:]
		ans = []
		even.reverse()
		while e < n // 2:
			ans.append(odd[o])
			ans.append(even[e])
			e += 1
			o += 1
		ans.append(odd[o])
		return ans


def reaching_height(n, arr):
	flag = 1
	if n == 1:
		return arr
	arr.sort()
	if arr[0] == arr[-1]:
		return [-1]
	i = 0
	j = n - 1
	l = []
	while i <= j:
		if flag == 1:
			l.append(arr[j])
			j -= 1
			flag = 0
		else:
			l.append(arr[i])
			i += 1
			flag = 1
	return l
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ans = reaching_height(n, arr)
	if len(ans) == 1 and ans[0] == -1:
		print('Not Possible')
	else:
		print(*ans)


def reaching_height(n, arr):
	arr.sort(reverse=True)
	if len(arr) > 1 and arr[0] <= arr[-1]:
		return [-1]
	t = []
	i = 0
	j = n - 1
	f = 1
	while i <= j:
		if f == 1:
			t.append(arr[i])
			i += 1
			f *= -1
		else:
			t.append(arr[j])
			j -= 1
			f *= -1
	return t
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ans = reaching_height(n, arr)
	if len(ans) == 1 and ans[0] == -1:
		print('Not Possible')
	else:
		print(*ans)


def reaching_height(n, arr):
	if n == 1:
		return arr
	arr.sort()
	i = 0
	j = n - 1
	result = [0 for i in range(n)]
	k = 0
	while i <= j:
		if k % 2 == 0:
			result[k] = arr[j]
			j -= 1
		else:
			result[k] = arr[i]
			i += 1
		k += 1
	if result[0] == result[-1]:
		return [-1]
	return result
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ans = reaching_height(n, arr)
	if len(ans) == 1 and ans[0] == -1:
		print('Not Possible')
	else:
		print(*ans)


from collections import deque

def reaching_height(n, arr):
	arr.sort()
	arr_odd = arr[n // 2:]
	arr_even = deque(arr[:n // 2])
	for i in range(1, len(arr) + 1):
		if i % 2 == 1:
			arr[i - 1] = arr_odd.pop()
		else:
			arr[i - 1] = arr_even.popleft()
	floor = 1
	for (index, item) in enumerate(arr):
		if index % 2 == 1:
			floor += item
		else:
			floor -= item
		if floor == 1:
			return [-1]
	return arr
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ans = reaching_height(n, arr)
	if len(ans) == 1 and ans[0] == -1:
		print('Not Possible')
	else:
		print(*ans)


def reaching_height(n, arr):
	if n == 1:
		return arr
	if len(set(arr)) == 1:
		return [-1]
	arr.sort()
	a = arr[0:n // 2].copy()
	b = arr[n // 2:].copy()
	b.reverse()
	j = 0
	for i in range(0, n, 2):
		arr[i] = b[j]
		arr[i + 1] = a[j]
		j += 1
		if n % 2 != 0 and i + 1 == n - 2:
			arr[n - 1] = b[-1]
			break
	return arr


def reaching_height(n, arr):
	arr.sort()
	lift = [None] * n
	(i, j) = (0, n - 1)
	height = 0
	for k in range(n):
		if k & 1:
			lift[k] = arr[i]
			height -= lift[k]
			i += 1
		else:
			lift[k] = arr[j]
			height += lift[k]
			j -= 1
		if height <= 0:
			return [-1]
	return lift


def reaching_height(n, arr):
	i = 0
	j = n - 1
	arr.sort()
	ans = [0] * n
	c = 0
	s = 0
	while i <= j:
		if (c + 1) % 2 == 0:
			ans[c] = arr[i]
			s -= arr[i]
			i += 1
		else:
			ans[c] = arr[j]
			s += arr[j]
			j -= 1
		c += 1
		if s <= 0:
			return [-1]
	if s <= 0:
		return [-1]
	return ans


def reaching_height(n, arr):
	arr.sort(reverse=True)
	numer = int(n / 2)
	lst = []
	lst1 = []
	for i in range(numer):
		j = -i - 1
		lst.append(arr[i])
		lst1.append(arr[i])
		lst.append(arr[j])
		lst1.append(-arr[j])
	if n % 2 != 0:
		lst.append(arr[numer])
	if sum(lst1) == 0 and lst1 != []:
		return [-1]
	else:
		return lst


import heapq

def reaching_height(n, arr):
	ans = [0] * n
	for (idx, _) in enumerate(arr):
		arr[idx] *= -1
	heapq.heapify(arr)
	flag = 1
	index = 0
	while arr:
		num = heapq.heappop(arr)
		ans[index] = abs(num)
		index = index + 2 if flag else index - 2
		if index >= n:
			flag = 0
			index = n - 1 if n % 2 == 0 else n - 2
	if len(ans) > 1:
		if ans[0] == ans[1]:
			return [-1]
	return ans


def reaching_height(n, arr):
	arr2 = [0] * n
	arr.sort()
	i = n - 1
	j = 0
	count = 0
	s = 'Not Possible'
	for a in range(len(arr) - 1):
		if arr[a] != arr[a + 1]:
			break
		count = count + 1
		if len(arr) <= 2 and arr[0] == arr[1]:
			return [-1]
		if count == len(arr) - 2:
			return [-1]
	while i >= n // 2:
		arr2[j] = arr[i]
		i = i - 1
		j = j + 2
	j = 1
	i = 0
	while i < n // 2:
		arr2[j] = arr[i]
		i = i + 1
		j = j + 2
	return arr2


def reaching_height(n, arr):
	arr.sort(reverse=True)
	if n % 2 == 0:
		a = arr[:n // 2]
		b = arr[n // 2:]
	else:
		a = arr[:n // 2 + 1]
		b = arr[n // 2 + 1:]
	b.sort()
	l = []
	su = 0
	for i in range(n // 2):
		l.append(a[i])
		l.append(b[i])
		su += a[i] - b[i]
		if su == 0:
			return [-1]
	if n % 2 == 1:
		l.append(a[-1])
		su += a[-1]
	if su == 0:
		return [-1]
	return l


def reaching_height(n, arr):
	if n == 1:
		return arr
	arr.sort()
	res = []
	s = set()
	(l, h) = (0, n - 1)
	while l <= h:
		s.add(arr[l])
		s.add(arr[h])
		if l == h:
			res.append(arr[h])
			l += 1
			h -= 1
			continue
		res.append(arr[h])
		res.append(arr[l])
		h -= 1
		l += 1
	if s == {arr[0]}:
		return [-1]
	else:
		return res


def reaching_height(n, arr):
	if n == 1:
		return arr
	p = arr.copy()
	p.sort()
	l = [0 for i in range(n)]
	(r, q) = (0, n - 1)
	count = 0
	for i in range(1, n + 1):
		if p[i - 1] == p[0]:
			count += 1
		if i % 2 != 0:
			l[i - 1] = p[q]
			q = q - 1
		else:
			l[i - 1] = p[r]
			r += 1
	if count == n:
		return [-1]
	return l


def reaching_height(n, arr):
	arr.sort()
	result = []
	height = 0
	for pos in range(n // 2):
		result.append(arr[-pos - 1])
		result.append(arr[pos])
	if n % 2 != 0:
		result.append(arr[n // 2])
	for pos in range(n):
		if pos % 2 == 0:
			height += result[pos]
		else:
			height -= result[pos]
		if height <= 0:
			return [-1]
	return result


def reaching_height(n, arr):
	arr.sort()
	ans = []
	if arr == [arr[0] for _ in range(n)]:
		if n == 1:
			return arr
		return [-1]
	for i in range(n):
		j = n - 1 - i
		if j <= i:
			if j == i:
				ans.append(arr[j])
			return ans
		ans.append(arr[j])
		ans.append(arr[i])


def reaching_height(n, arr):
	if n == 1:
		return arr
	arr.sort()
	i = 0
	j = n - 1
	ans = []
	flag = 0
	while i < j:
		ans.append(arr[j])
		ans.append(arr[i])
		flag += arr[i] - arr[j]
		j -= 1
		i += 1
		if flag == 0:
			return [-1]
		if j == i:
			ans.append(arr[j])
	return ans


def reaching_height(n, arr):
	arr.sort()
	a = len(arr)
	arr1 = []
	if a == 2 and arr[0] == arr[1]:
		arr1.append(-1)
		return arr1
	else:
		i = 0
		j = n - 1
		while i <= j:
			if i == j:
				arr1.append(arr[i])
				return arr1
			arr1.append(arr[j])
			arr1.append(arr[i])
			j = j - 1
			i = i + 1
		return arr1


def reaching_height(n, arr):
	arr.sort()
	mini = 0
	maxi = n - 1
	maxele = arr[n - 1] + 1
	for i in range(0, n):
		if i % 2 == 0:
			arr[i] += arr[maxi] % maxele * maxele
			maxi -= 1
		else:
			arr[i] += arr[mini] % maxele * maxele
			mini += 1
	floor = 0
	for i in range(0, n):
		arr[i] = arr[i] // maxele
		if i % 2 == 0:
			floor += arr[i]
		else:
			floor -= arr[i]
		if floor <= 0:
			return [-1]
	return arr


def reaching_height(n, arr):
	a = []
	arr.sort(reverse=True)
	j = 0
	k = n - 1
	i = 0
	ans = 0
	while i < n:
		if i % 2 == 0:
			a.append(arr[j])
			ans = ans + arr[j]
			j = j + 1
		else:
			a.append(arr[k])
			ans = ans - arr[k]
			k = k - 1
		i = i + 1
	if ans < 1:
		return [-1]
	else:
		return a


def reaching_height(n, arr):
	temp = sorted(arr)
	if len(arr) == 1:
		return arr
	if len(set(arr)) == 1:
		return [-1]
	arr.clear()
	arr = [0] * n
	p = 0
	q = len(temp) - 1
	for i in range(n):
		if i % 2 == 0:
			arr[i] = temp[q]
			q = q - 1
		else:
			arr[i] = temp[p]
			p = p + 1
	return arr


def reaching_height(n, arr):
	if n == 1:
		return arr
	arr.sort()
	if arr[0] == arr[n - 1]:
		return [-1]
	res = []
	f = 1
	l = 0
	r = n - 1
	while l <= r:
		if f == 1:
			res.append(arr[r])
			r -= 1
		else:
			res.append(arr[l])
			l += 1
		f *= -1
	return res


def reaching_height(n, arr):
	arr.sort()
	ans = [0] * n
	left = 0
	right = n - 1
	if n == 1:
		return arr
	for i in range(n):
		if i % 2 == 0:
			ans[i] = arr[right]
			right -= 1
		else:
			ans[i] = arr[left]
			left += 1
	for i in range(n - 1):
		if ans[i] == ans[i + 1]:
			if ans[i] == min(ans):
				ans = [-1]
				return ans
	return ans


def reaching_height(n, arr):
	v = []
	if n == 1:
		v.append(arr[0])
		return v
	arr.sort()
	if arr[0] == arr[n - 1]:
		v.append(-1)
		return v
	hi = n - 1
	lo = 0
	is_hi = 1
	while lo <= hi:
		if is_hi:
			v.append(arr[hi])
			hi -= 1
		else:
			v.append(arr[lo])
			lo += 1
		is_hi ^= 1
	return v


def reaching_height(n, arr):
	if len(arr) == 1:
		return [arr[0]]
	if len(arr) > 1:
		s = set(arr)
		if len(s) == 1:
			return [-1]
	p = sorted(arr, reverse=True)
	q = sorted(arr)
	a = []
	for i in range(n // 2):
		a.append(p[i])
		a.append(q[i])
	if len(arr) % 2 == 1:
		a.append(p[n // 2])
	return a


def reaching_height(n, arr):
	if n == 0:
		return [-1]
	if n == 1:
		return arr
	if len(set(arr)) == 1:
		return [-1]
	else:
		arr.sort()
		i = 0
		j = n - 1
		new_arr = []
		while i < j:
			new_arr.append(arr[j])
			new_arr.append(arr[i])
			i += 1
			j -= 1
			if j == i:
				new_arr.append(arr[j])
	return new_arr


def reaching_height(n, arr):
	if n == 1:
		return arr
	if n == 0 or len(set(arr)) == 1:
		return [-1]
	arr.sort()
	(i, j) = (0, n - 1)
	ans = []
	while i <= j:
		if i == j:
			ans.append(arr[i])
		else:
			ans.append(arr[j])
			ans.append(arr[i])
		i += 1
		j -= 1
	return ans


def reaching_height(n, arr):
	if n == 1:
		return arr
	odd = 0
	even = 0
	arr.sort()
	arr = arr[::-1]
	l = [0] * len(arr)
	l[0] = arr[0]
	even += l[0]
	for i in range(1, n // 2 + 1):
		l[2 * i - 1] = arr[-i]
		odd += arr[-i]
		if 2 * i < n:
			l[2 * i] = arr[i]
			even += arr[i]
	if even - odd < 1:
		return [-1]
	return l


def reaching_height(n, arr):
	arr.sort()
	arr.reverse()
	(a, lmax, lmin) = ([], [], [])
	for i in range(n):
		if i < n / 2:
			lmax.append(arr[i])
		else:
			lmin.append(arr[i])
	lmin.sort()
	for i in range(n):
		if i < len(lmax):
			a.append(lmax[i])
		if i < len(lmin):
			a.append(lmin[i])
	if len(a) == 1 or a[0] > a[n - 1]:
		return a
	return [-1]


def reaching_height(n, arr):
	arr.sort()
	li = []
	if n == 1:
		li.append(arr[0])
		return li
	if arr[0] == arr[n - 1]:
		li.append(-1)
		return li
	low = 0
	high = n - 1
	while low < high:
		li.append(arr[high])
		li.append(arr[low])
		high -= 1
		low += 1
	if n % 2:
		li.append(arr[low])
	return li


from typing import List

def reaching_height(n, arr):
	new_arr = sorted(arr)
	if n <= 1:
		return arr
	start_index = 0
	end_index = len(arr) - 1
	arr_i = 0
	while arr_i < n:
		arr[arr_i] = new_arr[end_index]
		if arr_i + 1 >= len(arr):
			break
		arr[arr_i + 1] = new_arr[start_index]
		arr_i += 2
		start_index += 1
		end_index -= 1
	is_odd = True
	curr_floor = 0
	for el in arr:
		if is_odd:
			curr_floor += el
		else:
			curr_floor -= el
			if curr_floor <= 0:
				return [-1]
		is_odd = not is_odd
	return arr


def reaching_height(n, arr):
	arr = sorted(arr, reverse=True)
	start = 0
	end = n - 1
	ans = []
	flag = 0
	while start <= end:
		ans.append(arr[start])
		flag += arr[start]
		if start != end:
			ans.append(arr[end])
			flag -= arr[end]
		start += 1
		end -= 1
	if flag == 0:
		ans.clear()
		ans.append(-1)
	return ans


def reaching_height(n, arr):
	A = []
	j = 0
	arr.sort(reverse=True)
	if n == 1:
		return arr
	for i in range(1, n + 1):
		if i % 2 != 0:
			A.append(arr[j])
		else:
			A.append(arr[n - 1 - j])
			j += 1
	if A[0] == A[n - 1]:
		return [-1]
	return A


def reaching_height(n, arr):
	temp = [-1]
	if n < 2:
		return arr
	if n > 1 and max(arr) == min(arr):
		return temp
	lista = []
	for i in range(n):
		lista.append(arr[i])
	lista.sort()
	k = 0
	m = n - 1
	for i in range(n):
		if i % 2 == 0:
			arr[i] = lista[m]
			m = m - 1
		else:
			arr[i] = lista[k]
			k = k + 1
	return arr


def reaching_height(n, arr):
	if n == 1:
		return arr
	if arr.count(arr[0]) == n:
		return [-1]
	arr.sort()
	arr = arr[::-1]
	l = [0] * len(arr)
	l[0] = arr[0]
	for i in range(1, n // 2 + 1):
		l[2 * i - 1] = arr[-i]
		if 2 * i < n:
			l[2 * i] = arr[i]
	return l


def reaching_height(n, arr):
	arr = sorted(arr)
	res = []
	n = len(arr)
	if len(arr) == 2:
		if len(set(arr)) != len(arr):
			return [-1]
	for i in range(len(arr)):
		if i < n // 2:
			res.append(arr[n - i - 1])
			res.append(arr[i])
	if n % 2 == 1:
		res.append(arr[n // 2])
	return res


def reaching_height(n, arr):
	arr.sort()
	newarr = [0] * n
	j = 1
	i = 0
	if n == 1:
		return arr
	result = arr.count(arr[0]) == len(arr)
	if result:
		return [-1]
	while i < n // 2:
		newarr[j] = arr[i]
		i += 1
		j += 2
	k = n - 1
	l = 0
	while k >= n // 2:
		newarr[l] = arr[k]
		k = k - 1
		l = l + 2
	return newarr


def reaching_height(n, arr):
	currentLevel = 0
	if n == 1:
		return [arr[0]]
	arr.sort()
	soln = []
	(i, j) = (n - 1, 0)
	while j <= i:
		if i == j:
			soln.append(arr[i])
			currentLevel += arr[i]
			break
		soln.append(arr[i])
		soln.append(arr[j])
		currentLevel += arr[i]
		currentLevel -= arr[j]
		if currentLevel == 0:
			return [-1]
		i -= 1
		j += 1
	return soln


def reaching_height(n, arr):
	if n == 1:
		return arr
	arr.sort()
	arr.reverse()
	k = n // 2
	if n % 2 != 0:
		k += 1
	ans = []
	s = 0
	for i in range(k):
		s = s + arr[i] - arr[n - i - 1]
		if s <= 0:
			return [-1]
		ans.append(arr[i])
		if i != k - 1 or n % 2 == 0:
			ans.append(arr[n - i - 1])
	return ans


def reaching_height(n, arr):
	arr.sort()
	s = 0
	i = 0
	j = n - 1
	b = []
	while i <= j:
		b.append(arr[j])
		s += arr[j]
		j -= 1
		if i <= j:
			b.append(arr[i])
			s -= arr[i]
			i += 1
	if s == 0:
		return [-1]
	else:
		return b


def reaching_height(n, arr):
	(newArray, l, r) = ([], 0, len(arr) - 1)
	arr.sort()
	if len(arr) == 1:
		return arr
	if len(arr) == 0 or arr[l] == arr[r]:
		return [-1]
	while l <= r:
		newArray.append(arr[r])
		r -= 1
		if l <= r:
			newArray.append(arr[l])
			l += 1
	return newArray


def reaching_height(n, arr):
	arr.sort(reverse=True)
	if arr[0] == arr[n - 1] and n > 1:
		return [-1]
	ans = [0] * n
	j = 0
	for i in range(0, n, 2):
		ans[i] = arr[j]
		j += 1
	j = n - 1
	for i in range(1, n, 2):
		ans[i] = arr[j]
		j -= 1
	return ans


def reaching_height(n, arr):
	if len(arr) == 1:
		return arr
	if max(arr) == min(arr):
		return [-1]
	arr.sort()
	res = []
	i = 0
	j = n - 1
	while i < j:
		res.append(arr[j])
		j -= 1
		res.append(arr[i])
		i += 1
	if len(arr) % 2 == 1:
		res.append(arr[i])
	return res


def reaching_height(n, arr):
	if n == 1:
		return arr
	if arr.count(arr[0]) == n:
		return [-1]
	else:
		arr.sort()
		l = n - 1
		r = 0
		ans = []
		for i in range(n):
			if i % 2 == 0:
				ans.append(arr[l])
				l -= 1
			else:
				ans.append(arr[r])
				r += 1
		return ans