Given an array A of n elements, rearrange the array according to the following relations :
 , if i is even.
 , if i is odd.[Considering 1-indexed array]
Return the resultant array.
Example:
Input 1:
A[] = {1, 2, 2, 1}
Output:
1 2 1 2
Explanation:
Both 2 are at even positions and 1 at odd satisfying 
given condition 
Input 2:
A[] = {1, 3, 2}
Output:
1 3 2
Explanation:
Here, the array is already sorted as per the conditions.
 
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 assign() that takes an array (arr), sizeOfArray (n), and return the resultant array.
Note: Generated output will depict whether your returned answer is correct or wrong
Expected Time Complexity: O(NLOG(N)).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ arr[i] ≤ 10^{6}

Difficulty: EASY
Tags: Sorting

Data structures
Skill types: Sorting

Data structures
Expected Time Complexity: O(NLOG(N)).
Expected Auxiliary Space: O(1).

Starter code:
#User function Template for python3



class Solution:

    def assign (self, arr,  n) : 

        #Complete the function



Solutions:
class Solution:

	def assign(self, arr, n):
		arr.sort()
		last = n - 1
		first = 0
		lst = [0] * n
		for i in range(n):
			if (i + 1) % 2 == 0:
				lst[i] = arr[last]
				last -= 1
			else:
				lst[i] = arr[first]
				first += 1
		return lst


class Solution:

	def assign(self, arr, n):
		arr.sort()
		if n == 1 or n == 2:
			return arr
		if n % 2 == 0:
			for i in range(1, n - 1, 2):
				(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
		else:
			for i in range(1, n, 2):
				(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
		return arr


class Solution:

	def assign(self, arr, n):
		arr.sort()
		res = [0] * n
		p = 0
		q = n - 1
		for i in range(n):
			if (i + 1) % 2 == 0:
				res[i] = arr[q]
				q = q - 1
			else:
				res[i] = arr[p]
				p = p + 1
		return res


class Solution:

	def assign(self, arr, n):
		arr.sort()
		start = n - 1
		end = 0
		a = [0] * n
		for i in range(0, n):
			if (i + 1) % 2 == 0:
				a[i] = arr[start]
				start = start - 1
			else:
				a[i] = arr[end]
				end = end + 1
		return a


class Solution:

	def assign(self, nums, n):
		nums.sort()
		(start, end) = (0, len(nums) - 1)
		result_ = [0] * len(nums)
		for i in range(len(nums)):
			if i % 2 != 0:
				result_[i] = nums[end]
				end -= 1
			else:
				result_[i] = nums[start]
				start += 1
		return result_


class Solution:

	def assign(self, arr, n):
		arr.sort()
		for i in range(n):
			if i == 0:
				continue
			if i % 2 != 0:
				if arr[i] < arr[i - 1]:
					temp = arr[i]
					arr[i] = arr[i - 1]
					arr[i - 1] = temp
			elif arr[i] > arr[i - 1]:
				temp = arr[i]
				arr[i] = arr[i - 1]
				arr[i - 1] = temp
		return arr


class Solution:

	def assign(self, arr, n):
		arr.sort()
		mid = n // 2
		a = arr[0:mid]
		b = arr[mid:-1]
		b.sort(reverse=True)
		c = []
		for i in range(len(b)):
			if i % 2 == 0:
				c.append(a[i])
			elif i % 2 == 1:
				c.append(b[i])
		return c


class Solution:

	def assign(self, arr, n):
		arr.sort()
		temp = [0] * n
		s = 0
		l = n - 1
		for i in range(n):
			if (i + 1) % 2 == 0:
				temp[i] = arr[l]
				l -= 1
			else:
				temp[i] = arr[s]
				s += 1
		for i in range(n):
			arr[i] = temp[i]
		return arr


class Solution:

	def assign(self, arr, n):
		arr.sort()
		i = 1
		while i < n - 1:
			(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
			i += 2
		return arr


class Solution:

	def assign(self, arr, n):
		k = arr.copy()
		lis = []
		k.sort()
		j = 0
		m = n - 1
		for i in range(0, n, 2):
			lis.append(k[j])
			lis.append(k[m])
			if j < m:
				j += 1
				m -= 1
		for i in range(n):
			arr[i] = lis[i]
		return arr


class Solution:

	def assign(self, arr, n):
		arr.sort()
		for i in range(1, n - 1, 2):
			(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
		return arr


class Solution:

	def assign(self, a, n):
		a.sort()
		ans = [0] * n
		p = 0
		q = n - 1
		for i in range(n):
			if (i + 1) % 2 == 0:
				ans[i] = a[q]
				q = q - 1
			else:
				ans[i] = a[p]
				p = p + 1
		return ans


class Solution:

	def assign(self, arr, n):
		arr.sort()
		i = 0
		j = n - 1
		output = []
		while i < j:
			output.append(arr[i])
			output.append(arr[j])
			i += 1
			j -= 1
		if i == j:
			output.append(arr[i])
		return output


class Solution:

	def assign(self, arr, n):
		arr.sort()
		a = len(arr) // 2 + 1
		if len(arr) % 2 == 0:
			a = len(arr) // 2
		for i in range(len(arr) - 1):
			if i % 2 == 1:
				b = arr[i]
				arr[i] = arr[a]
				arr[a] = b
				a += 1
		return arr


class Solution:

	def assign(self, arr, n):
		arr.sort()
		s = 0
		e = n - 1
		ans = [0] * n
		for i in range(n):
			if (i + 1) % 2 == 0:
				ans[i] = arr[e]
				e -= 1
			else:
				ans[i] = arr[s]
				s += 1
		return ans


class Solution:

	def assign(self, arr, n):
		arr.sort()
		for i in range(1, n):
			if i + 1 & 1 and arr[i] > arr[i - 1]:
				(arr[i], arr[i - 1]) = (arr[i - 1], arr[i])
			if i + 1 & 1 == 0 and arr[i] < arr[i - 1]:
				(arr[i], arr[i - 1]) = (arr[i - 1], arr[i])
		return arr


class Solution:

	def assign(self, arr, n):
		start = 0
		end = n - 1
		arr.sort(reverse=True)
		arr1 = [0] * n
		for i in range(n):
			if (i + 1) % 2 == 0:
				arr1[i] = arr[start]
				start += 1
			else:
				arr1[i] = arr[end]
				end -= 1
		return arr1


class Solution:

	def assign(self, arr, n):
		li = [0] * len(arr)
		arr.sort()
		i = 0
		j = len(arr) - 1
		for n in range(len(arr)):
			if (n + 1) % 2 == 0:
				li[n] = arr[j]
				j -= 1
			else:
				li[n] = arr[i]
				i += 1
		return li


class Solution:

	def assign(self, arr, n):
		a = arr
		arr = sorted(arr)
		p = 0
		q = n - 1
		for i in range(n):
			if (i + 1) % 2 == 0:
				a[i] = arr[q]
				q = q - 1
			else:
				a[i] = arr[p]
				p = p + 1
		return a


class Solution:

	def assign(self, arr, n):
		arr.sort()
		ans = [None] * n
		small = 0
		large = n - 1
		for i in range(n):
			if i % 2 != 0:
				ans[i] = arr[large]
				large -= 1
			else:
				ans[i] = arr[small]
				small += 1
		return ans


class Solution:

	def assign(self, arr, n):
		arr = sorted(arr)
		i = 1
		while i < len(arr) - 1:
			x = arr[i]
			y = arr[i + 1]
			arr[i + 1] = x
			arr[i] = y
			i += 2
		return arr


class Solution:

	def assign(self, arr, n):
		sorted_array = []
		sorted_array = sorted(arr)
		j = 0
		k = n - 1
		for i in range(len(arr)):
			if (i + 1) % 2 == 0:
				arr[i] = sorted_array[k]
				k -= 1
			else:
				arr[i] = sorted_array[j]
				j += 1
		return arr


class Solution:

	def assign(self, arr, n):
		arr.sort()
		res = [0] * n
		l = 0
		r = n - 1
		for i in range(n):
			if i % 2 == 0:
				res[i] = arr[l]
				l += 1
			else:
				res[i] = arr[r]
				r -= 1
		return res


class Solution:

	def assign(self, arr, n):
		a = sorted(arr)
		for i in range(1, len(arr) - 1, 2):
			(a[i], a[i + 1]) = (a[i + 1], a[i])
		return a


class Solution:

	def assign(self, arr, n):
		arr.sort()
		half = 0
		if n % 2 == 0:
			half = n / 2 - 1
		else:
			half = n // 2
		l = []
		h = []
		myArr = []
		for i in range(n):
			if i <= half:
				l.append(arr[i])
			else:
				h.append(arr[i])
			myArr.append(0)
		length = 0
		i = 0
		while i != n and length < len(l):
			myArr[i] = l[length]
			length += 1
			i += 2
		length = len(h) - 1
		i = 1
		while i != n and length >= 0:
			myArr[i] = h[length]
			length -= 1
			i += 2
		return myArr


class Solution:

	def assign(self, arr, n):
		arr.sort()
		result = []
		start = 0
		end = n - 1
		while start <= end:
			result.append(arr[start])
			result.append(arr[end])
			start += 1
			end -= 1
		arr[:] = result[:]
		return arr


class Solution:

	def assign(self, arr, n):
		arr.sort()
		i = 0
		j = n - 1
		b = []
		while i <= j:
			b.append(arr[i])
			i += 1
			if i > j:
				break
			b.append(arr[j])
			j -= 1
		return b


class Solution:

	def assign(self, arr, n):
		arr.sort()
		op = [0] * n
		p = 0
		l = n - 1
		for i in range(n):
			if (i + 1) % 2 == 0:
				op[i] = arr[l]
				l -= 1
			else:
				op[i] = arr[p]
				p += 1
		return op


class Solution:

	def assign(self, arr, n):
		temp = arr[:]
		temp.sort(reverse=True)
		j = 0
		for i in range(1, n, 2):
			arr[i] = temp[j]
			j += 1
		j = n - 1
		for i in range(0, n, 2):
			arr[i] = temp[j]
			j -= 1
		return arr


from collections import Counter

class Solution:

	def assign(self, arr, n):
		arr.sort()
		li = []
		r = n - 1
		l = 0
		i = 0
		while l < r:
			if i % 2 == 0:
				li.append(arr[l])
				l += 1
			else:
				li.append(arr[r])
				r -= 1
			i += 1
		return li


class Solution:

	def assign(self, arr, n):
		arr.sort()
		temp = [0] * n
		p = 0
		q = n - 1
		for i in range(n):
			if (i + 1) % 2 == 0:
				temp[i] = arr[q]
				q -= 1
			else:
				temp[i] = arr[p]
				p += 1
		return temp

def checkOrder(res):
	for i in range(len(res)):
		if i % 2 != 0:
			if res[i] < res[i - 1]:
				return False
		elif res[i] > res[i - 1]:
			return False
	return True
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ob = Solution()
	res = ob.assign(arr, n)
	if checkOrder(res):
		print('Correct')
	else:
		print('Wrong Answer')


class Solution:

	def assign(self, arr, n):
		arr.sort()
		o = arr[:n // 2]
		e = arr[n // 2:][::-1]
		res = []
		for i in range(n // 2):
			res.extend([o[i], e[i]])
		return res


class Solution:

	def assign(self, arr, n):
		arr1 = arr.copy()
		arr1.sort()
		j = 0
		k = n - 1
		for i in range(0, n):
			if i % 2 != 0:
				arr[i] = arr1[k]
				k -= 1
			else:
				arr[i] = arr1[j]
				j += 1
		return arr


class Solution:

	def assign(self, arr, n):
		f = []
		arr.sort()
		c = 0
		n = 0
		for i in range(n):
			f.append(0)
		for i in range(n):
			if i % 2 == 0 and c < n:
				f[c] = arr[i]
				c = c + 2
				n = n + 1
		c = 1
		for j in range(n):
			if j % 2 == 1 and c < n:
				f[c] = arr[n]
				c = c + 2
		return f