Given an array arr of size n. Arrange the elements of the array in a way similar to the to-and-fro movement of a Pendulum.
	The minimum element out of the list of integers, must come in center position of array. If there are even elements, then minimum element should be moved to (n-1)/2 index (considering that indexes start from 0)
	The next number (next to minimum) in the ascending order, goes to the right, the next to next number goes to the left of minimum number and it continues like a Pendulum.
	As higher numbers are reached, one goes to one side in a to-and-fro manner similar to that of a Pendulum
Example 1:
Input : 
n = 5
arr[] = {1, 3, 2, 5, 4}
Output :
5 3 1 2 4
Explanation: 
The minimum element is 1, so it is 
moved to the middle. The next higher
element 2  is moved to the right of 
the middle element while the next 
higher element 3 is moved to the left 
of the middle element and this process
is continued.
Example 2:
Input :
n = 5 
arr[] = {11, 12, 31, 14, 5}
Output :
31 12 5 11 14
Your Task:  
You don't need to read input or print anything. Your task is to complete the function pendulumArrangement() which takes the array arr[] and its size n as inputs and returns  the vector array in Pendulum Arrangement.
Expected Time Complexity: O(n. Log(n))
Expected Auxiliary Space: O(n)
Constraints:
	1 <= n <= 10^{5}
	0 <= arr[i] <= 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3



def pendulumArrangement( arr, n):

    

    

Solutions:
def pendulumArrangement(arr, n):
	arr.sort()
	a = []
	b = []
	for i in range(1, n, 2):
		a.append(arr[i])
	for i in range(0, n, 2):
		b.append(arr[i])
	b = b[::-1]
	b = b + a
	return b


def pendulumArrangement(arr, n):
	arr.sort(reverse=True)
	result = []
	for i in range(n):
		result.append(0)
	left = 0
	left_index = 0
	right_index = n - 1
	while left < n:
		result[left_index] = arr[left]
		if left + 1 < n:
			result[right_index] = arr[left + 1]
		left_index = left_index + 1
		right_index = right_index - 1
		left = left + 2
	if n % 2 == 0:
		result = result[::-1]
	return result


import math

def pendulumArrangement(arr, n):
	arr.sort()
	newcounter = n // 2 + n % 2 - 1
	arro = list(arr)
	for (i, elem) in enumerate(arr):
		if i % 2 == 0:
			newcounter -= i
		else:
			newcounter += i
		arr[newcounter] = arro[i]
	return arr


def pendulumArrangement(arr, n):
	arr.sort()
	c = []
	b = []
	c.append(arr[0])
	for i in range(1, n):
		if i % 2 == 0:
			c.append(arr[i])
	c.reverse()
	for i in range(0, n):
		if i % 2 != 0:
			b.append(arr[i])
	c.extend(b)
	return c


def pendulumArrangement(arr, n):
	arr.sort()
	ryt = []
	lft = []
	for i in range(n):
		if i % 2 == 0:
			ryt.append(arr[i])
		else:
			lft.append(arr[i])
	ryt.reverse()
	return ryt + lft


def pendulumArrangement(arr, n):
	arr.sort()
	even = []
	odd = []
	for i in range(len(arr)):
		if i % 2 == 0:
			even.append(arr[i])
		else:
			odd.append(arr[i])
	even.reverse()
	return even + odd


def pendulumArrangement(arr, n):
	arr.sort()
	a = []
	b = []
	for i in range(len(arr)):
		if i % 2 == 0:
			a.append(arr[i])
		else:
			b.append(arr[i])
	a.reverse()
	return a + b


def pendulumArrangement(arr, n):
	arr.sort(reverse=True)
	p = [0] * n
	mid = n // 2 if n % 2 == 1 else (n - 1) // 2
	start = 0
	for index in range(0, n // 2, 1):
		p[index] = arr[start]
		p[-index - 1] = arr[start + 1]
		start += 2
	p[mid] = arr[-1] if n % 2 == 1 else p[mid]
	p[:] = p[::-1] if n % 2 == 0 else p
	return p


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


def pendulumArrangement(arr, n):
	arr = sorted(arr)[::-1]
	l = []
	ll = []
	for i in range(len(arr) - 2, -1, -2):
		l.append(arr[i])
		ll.append(arr[i + 1])
	if len(arr) % 2 == 1:
		return [max(arr)] + ll[::-1] + l
	else:
		return ll[::-1] + l


def pendulumArrangement(arr, n):
	arr.sort()
	ans = []
	if n % 2 != 0:
		i = n - 1
		while i >= 0:
			ans.append(arr[i])
			i -= 2
		i = 1
		while i < n:
			ans.append(arr[i])
			i += 2
		return ans
	else:
		i = n - 2
		while i >= 0:
			ans.append(arr[i])
			i -= 2
		i = 1
		while i < n:
			ans.append(arr[i])
			i += 2
		return ans


def pendulumArrangement(arr, n):
	left = []
	right = []
	arr.sort()
	mid = [arr[0]]
	if n % 2 != 0:
		for i in range(1, n, 2):
			right.append(arr[i])
		for i in range(n - 1, 1, -2):
			left.append(arr[i])
	if n % 2 == 0:
		for i in range(1, n, 2):
			right.append(arr[i])
		for i in range(n - 2, 1, -2):
			left.append(arr[i])
	return left + mid + right


def pendulumArrangement(arr, n):
	arr.sort()
	i = 1
	x = [arr[0]]
	y = []
	while i < n - 1:
		x.append(arr[i])
		y.append(arr[i + 1])
		i += 2
	if n % 2 == 0:
		x.append(arr[-1])
	return y[::-1] + x


def pendulumArrangement(arr, n):
	res = [0] * n
	arr.sort(reverse=True)
	l = 0
	r = n - 1
	length = int(not n % 2)
	for i in range(n):
		if i % 2 == length:
			res[l] = arr[i]
			l += 1
		else:
			res[r] = arr[i]
			r -= 1
	return res


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


def pendulumArrangement(arr, n):
	arr.sort()
	x = n // 2
	b = [0] * n
	if n % 2 != 0:
		b[x] = arr[0]
		flg = 0
		j = 1
		z = 1
		for i in range(1, n):
			if flg == 0:
				b[x + j] = arr[i]
				j += 1
				flg = 1
			else:
				b[x - z] = arr[i]
				z += 1
				flg = 0
	else:
		x = x - 1
		b[x] = arr[0]
		flg = 0
		j = 1
		z = 1
		for i in range(1, n):
			if flg == 0:
				b[x + j] = arr[i]
				j += 1
				flg = 1
			else:
				b[x - z] = arr[i]
				z += 1
				flg = 0
	return b


def pendulumArrangement(arr, n):
	if n % 2 == 0:
		i = int((n - 1) / 2)
	else:
		i = int(n / 2)
	j = i + 1
	s = sorted(arr)
	l = 0
	tmp = [0] * n
	while i >= 0 or j < n or l < n:
		if i > 0 or l < n:
			tmp[i] = s[l]
			l += 1
		if j < n or l < n:
			tmp[j] = s[l]
			l += 1
		i -= 1
		j += 1
	return tmp


def pendulumArrangement(arr, n):
	if n % 2 == 0:
		l = n // 2 - 1
	else:
		l = n // 2
	d = []
	for i in range(n):
		d.append(1)
	arr.sort()
	d[l] = arr[0]
	m = l
	m1 = l
	for i in range(1, n):
		if i % 2 != 0:
			m += 1
			d[m] = arr[i]
		else:
			m1 -= 1
			d[m1] = arr[i]
	return d


def pendulumArrangement(arr, n):
	if n % 2 == 0:
		l = n // 2 - 1
	else:
		l = n // 2
	p = []
	for i in range(n):
		p.append(1)
	arr.sort()
	p[l] = arr[0]
	md = l
	ms = l
	for i in range(1, n):
		if i % 2 != 0:
			md += 1
			p[md] = arr[i]
		else:
			ms -= 1
			p[ms] = arr[i]
	return p


def pendulumArrangement(arr, n):
	l1 = []
	l2 = []
	arr.sort()
	for i in range(len(arr)):
		if i % 2 == 0:
			l1.append(arr[i])
		else:
			l2.append(arr[i])
	return l1[::-1] + l2


def pendulumArrangement(arr, n):
	arr.sort()
	out_arr = [0] * n
	mid = (n - 1) // 2
	i = 1
	j = 1
	out_arr[mid] = arr[0]
	for i in range(1, mid + 1):
		out_arr[mid + i] = arr[j]
		j += 1
		out_arr[mid - i] = arr[j]
		j += 1
	if len(arr) == 2:
		return arr
	if int(n % 2) == 0:
		out_arr[mid + i + 1] = arr[j]
	return out_arr


def pendulumArrangement(arr, n):
	arr.sort()
	ev = []
	od = []
	for i in range(n):
		if i % 2 == 0:
			ev.append(arr[i])
		else:
			od.append(arr[i])
	ev[:] = ev[::-1]
	m = ev + od
	return m


def pendulumArrangement(arr, n):
	arr.sort()
	k1 = []
	k2 = []
	for i in range(n):
		if i % 2 == 0:
			k1.append(arr[i])
		elif i % 2 == 1:
			k2.append(arr[i])
	k1.reverse()
	a = k1 + k2
	return a


def pendulumArrangement(arr, n):
	arr.sort()
	b = [0] * n
	b[(n - 1) // 2] = arr[0]
	j = (n - 1) // 2 + 1
	for i in range(1, n, 2):
		b[j] = arr[i]
		j += 1
	j = (n - 1) // 2 - 1
	for i in range(2, n, 2):
		b[j] = arr[i]
		j -= 1
	return b


def pendulumArrangement(arr, n):
	arr.sort()
	arr1 = [0] * n
	j = 0
	for i in arr:
		arr1[j] = i
		j += 1
	mid = (n - 1) // 2
	arr[mid] = arr1[0]
	i = 1
	j = 1
	while i < n:
		arr[mid + j] = arr1[i]
		i += 2
		j += 1
	i = 0
	if n % 2 == 0:
		j = n - 2
	else:
		j = n - 1
	while i < mid:
		arr[i] = arr1[j]
		j -= 2
		i += 1
	return arr


def pendulumArrangement(arr, n):
	temp = [0] * n
	arr = sorted(arr)
	mid = (n - 1) // 2
	temp[mid] = arr[0]
	j = 1
	i = 1
	while i < mid + 1:
		temp[mid + i] = arr[j]
		j += 1
		temp[mid - i] = arr[j]
		j += 1
		i += 1
	if n % 2 == 0:
		temp[mid + i] = arr[j]
	for k in range(n):
		arr[k] = temp[k]
	return arr


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


def pendulumArrangement(arr, n):
	arr.sort()
	left = []
	right = []
	for i in range(n):
		if i % 2 == 0:
			left.append(arr[i])
		else:
			right.append(arr[i])
	left.reverse()
	return left + right


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


def pendulumArrangement(arr, n):
	arr.sort()
	leftArr = []
	rightArr = []
	for i in range(n):
		if i % 2 == 0:
			leftArr.append(arr[i])
		else:
			rightArr.append(arr[i])
	return leftArr[::-1] + rightArr


def pendulumArrangement(arr, n):
	arr.sort()
	arr1 = arr[0::2]
	arr2 = arr[1::2]
	return arr1[::-1] + arr2


def pendulumArrangement(arr, n):
	x1 = []
	l1 = sorted(arr)
	for i in range(2, n, 2):
		x1.append(l1[i])
	x1 = sorted(x1, reverse=True)
	x1.append(min(l1))
	for i in range(1, n, 2):
		x1.append(l1[i])
	return x1


def pendulumArrangement(arr, n):
	res = [None] * n
	ind = (n - 1) // 2
	arr.sort()
	res[ind] = arr[0]
	if n == 1:
		return res
	ptr = ind + 1
	for i in range(1, n, 2):
		res[ptr] = arr[i]
		ptr += 1
	ptr = ind - 1
	for i in range(2, n, 2):
		res[ptr] = arr[i]
		ptr -= 1
	return res


def pendulumArrangement(arr, n):
	b = sorted(arr)
	if n % 2 == 0:
		i = (n - 1) // 2
		arr[-1] = b[-1]
	else:
		i = n // 2
	(j, k) = (1, i + 1)
	arr[i] = b[0]
	i -= 1
	while j < n - 1:
		arr[k] = b[j]
		k += 1
		arr[i] = b[j + 1]
		i -= 1
		j += 2
	return arr


def pendulumArrangement(arr, n):
	arr.sort()
	result = []
	for i in range(0, n):
		result.append(0)
	k = int((n - 1) / 2)
	j = 1
	ind = 0
	flag = True
	while ind <= n - 1:
		if flag:
			flag = False
			result[k] = arr[ind]
			ind = ind + 1
			k = k + j
			j = j + 1
		else:
			flag = True
			result[k] = arr[ind]
			ind = ind + 1
			k = k - j
			j = j + 1
	return result


def pendulumArrangement(arr, n):
	arr.sort()
	krr = [0] * n
	(i, j) = (0, n - 1)
	if n % 2 == 0:
		for pos in range(n - 1, -1, -2):
			krr[j] = arr[pos]
			j -= 1
			pos -= 1
			krr[i] = arr[pos]
			i += 1
			pos -= 1
		return krr
	else:
		for pos in range(n - 1, 0, -2):
			krr[i] = arr[pos]
			i += 1
			pos -= 1
			krr[j] = arr[pos]
			j -= 1
			pos -= 1
		krr[n // 2] = arr[0]
		return krr


def pendulumArrangement(arr, n):
	li = []
	li2 = []
	arr.sort()
	li.append(arr[0])
	for i in range(1, n):
		if i % 2 != 0:
			li.append(arr[i])
		else:
			li2.append(arr[i])
	li2.reverse()
	li2.extend(li)
	return li2


def pendulumArrangement(arr, n):
	arr.sort()
	right_side = [arr[i] for i in range(1, n, 2)]
	left_side = [arr[i] for i in range(0, n, 2)]
	left_side.reverse()
	arr = left_side + right_side
	return arr


def pendulumArrangement(arr, n):
	temp = [0] * n
	arr.sort()
	if n % 2 == 0:
		index = (n - 1) // 2
	else:
		index = n // 2
	high = index + 1
	count = 0
	while index >= 0 or high < n or count < n:
		if index > 0 or count < n:
			temp[index] = arr[count]
			count += 1
		if high < n or count < n:
			temp[high] = arr[count]
			count += 1
		index -= 1
		high += 1
	return temp


def pendulumArrangement(arr, n):
	arr.sort()
	li = [0] * n
	mid = n // 2
	left = mid - 1
	right = mid + 1
	li[mid] = arr[0]
	i = 1
	while left >= 0 and right < n:
		li[left] = arr[i]
		i += 1
		left -= 1
		li[right] = arr[i]
		i += 1
		right += 1
	while left >= 0:
		li[left] = arr[i]
		i += 1
		left -= 1
	while right < n:
		li[right] = arr[i]
		i += 1
		right += 1
	li.reverse()
	return li


def pendulumArrangement(arr, n):
	arr.sort()
	x = min(arr)
	even = []
	odd = []
	for i in range(1, n):
		if i % 2 == 0:
			even.append(arr[i])
		else:
			odd.append(arr[i])
	rev = even[::-1]
	rev.append(x)
	return rev + odd


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


def pendulumArrangement(arr, n):
	arr = sorted(arr)
	a = [arr[i] for i in range(1, n, 2)]
	b = [arr[i] for i in range(0, n, 2)][::-1]
	return b + a


def pendulumArrangement(arr, n):
	arr.sort()
	lis = []
	kit = []
	jil = []
	jil.append(arr[0])
	ar = []
	i = 1
	while i < n:
		lis.append(arr[i])
		i += 1
		if n > i:
			kit.append(arr[i])
			i += 1
	ar += kit[::-1]
	ar += jil
	ar += lis
	return ar


def pendulumArrangement(arr, n):
	arr.sort()
	b = arr + []
	if n % 2 == 1:
		i = n // 2
		j = 0
		k = 1
		arr[i] = b[j]
		while j + 2 <= n - 1:
			arr[i + k] = b[j + 1]
			if i - k >= 0:
				arr[i - k] = b[j + 2]
			j += 2
			k += 1
	if n % 2 == 0:
		i = n // 2 - 1
		j = 0
		k = 1
		arr[i] = b[j]
		while j + 2 <= n - 1:
			arr[i + k] = b[j + 1]
			if i - k >= 0:
				arr[i - k] = b[j + 2]
			j += 2
			k += 1
	return arr


def pendulumArrangement(arr, n):
	arr.sort()
	p = n // 2
	l = arr[2:n:2][::-1]
	l.append(arr[0])
	l.extend(arr[1:n:2])
	return l


def pendulumArrangement(arr, n):
	mid = (n - 1) // 2
	result = [None] * n
	arr.sort()
	result[mid] = arr[0]
	x = mid + 1
	for i in range(1, len(arr), 2):
		result[x] = arr[i]
		x = x + 1
	if len(arr) % 2 == 0:
		y = 0
		for j in range(len(arr) - 2, 0, -2):
			if y < mid:
				result[y] = arr[j]
				y = y + 1
	else:
		y = 0
		for j in range(len(arr) - 1, 0, -2):
			if y < mid:
				result[y] = arr[j]
				y = y + 1
	return result


def pendulumArrangement(arr, n):
	z = [0] * n
	arr.sort()
	if n % 2 != 0:
		mid = int(n / 2)
	else:
		mid = int(n / 2) - 1
	z[mid] = arr[0]
	j = mid
	k = mid
	for i in range(1, n):
		if i % 2 == 0:
			j -= 1
			z[j] = arr[i]
		else:
			k += 1
			z[k] = arr[i]
	return z


def pendulumArrangement(arr, n):
	arr.sort()
	new_arr = [0] * n
	mid = n // 2 - 1 if n % 2 == 0 else n // 2
	new_arr[mid] = arr[0]
	j = 1
	for i in range(1, mid + 1):
		new_arr[mid + i] = arr[j]
		j += 1
		new_arr[mid - i] = arr[j]
		j += 1
	if n % 2 == 0:
		new_arr[n - 1] = arr[j]
	return new_arr


def pendulumArrangement(arr, n):
	if n % 2 != 0:
		a = []
		j = 0
		k = n - 2
		arr.sort(reverse=True)
		for i in range(n):
			if i == n // 2:
				a.append(arr[n - 1])
			elif i < n // 2:
				a.append(arr[j])
				j += 2
			elif i > n // 2:
				a.append(arr[k])
				k -= 2
	else:
		a = [0 for i in range(n)]
		j = 0
		k = n - 1
		arr.sort(reverse=True)
		for i in range(n - 1, -1, -1):
			if i < n // 2:
				a[i] = arr[k]
				k -= 2
			elif i >= n // 2:
				a[i] = arr[j]
				j += 2
	return a


def pendulumArrangement(arr, n):
	arr.sort()
	x = []
	y = []
	x.append(arr[0])
	for i in range(1, n):
		if i % 2 == 1:
			x.append(arr[i])
		else:
			y.append(arr[i])
	y.reverse()
	return y + x


def pendulumArrangement(arr, n):
	sort_arr = sorted(arr)
	lst = [sort_arr[0]]
	lst1 = []
	for i in range(1, n):
		if i % 2 != 0:
			lst.append(sort_arr[i])
		else:
			lst1.append(sort_arr[i])
	return lst1[::-1] + lst


def pendulumArrangement(arr, n):
	arr.sort()
	op = [0] * n
	mid = int((n - 1) / 2)
	a = mid
	b = mid
	op[mid] = arr[0]
	for i in range(n):
		if i % 2 == 1:
			op[a + 1] = arr[i]
			a += 1
		elif i % 2 == 0:
			op[b - i] = arr[i]
			b += 1
	return op


def pendulumArrangement(arr, n):
	lst = [0] * n
	arr.sort()
	if n % 2 == 0:
		mid = (n - 1) // 2
	else:
		mid = n // 2
	lst[mid] = arr[0]
	left = mid
	right = mid
	for i in range(1, n):
		if i % 2 == 1:
			lst[left + 1] = arr[i]
			left += 1
		elif i % 2 == 0:
			lst[right - 1] = arr[i]
			right -= 1
	return lst


def pendulumArrangement(arr, n):
	m = min(arr)
	mid = n // 2
	arr.sort()
	rarr = []
	larr = []
	for i in range(1, n):
		if i % 2 != 0:
			rarr.append(arr[i])
		else:
			larr.append(arr[i])
	larr.sort(reverse=True)
	res = larr + [m] + rarr
	return res


def pendulumArrangement(arr, n):
	res = [0] * n
	k = n // 2
	arr.sort()
	i = 0
	for x in range(0, n):
		if x % 2 != 0:
			i += 1
		if x == 0:
			res[k] = arr[x]
		elif x % 2 == 0:
			res[k + i] = arr[x]
		elif x % 2 != 0:
			res[k - i] = arr[x]
	return res[::-1]


def pendulumArrangement(arr, n):
	l = []
	r = []
	x = arr[0]
	arr.sort()
	for i in range(1, n):
		if i % 2 == 0:
			r.append(arr[i])
		else:
			l.append(arr[i])
	k = []
	r.sort(reverse=True)
	for i in range(len(r)):
		k.append(r[i])
	k.append(arr[0])
	for i in range(len(l)):
		k.append(l[i])
	return k

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		arr = [int(x) for x in input().strip().split()]
		answer = pendulumArrangement(arr, n)
		print(*answer)
		T -= 1
if __name__ == '__main__':
	main()


def pendulumArrangement(arr, n):
	arr.sort()
	a = []
	b = []
	for i in range(n):
		if i % 2 == 0:
			a.append(arr[i])
		else:
			b.append(arr[i])
	a.reverse()
	return a + b

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		arr = [int(x) for x in input().strip().split()]
		answer = pendulumArrangement(arr, n)
		print(*answer)
		T -= 1
if __name__ == '__main__':
	main()