Given a sorted array of positive integers. Your task is to rearrange the array elements alternatively i.e first element should be max value, second should be min value, third should be second max, fourth should be second min and so on.
Note: Modify the original array itself. Do it without using any extra space. You do not have to return anything.
Example 1:
Input:
n = 6
arr[] = {1,2,3,4,5,6}
Output: 6 1 5 2 4 3
Explanation: Max element = 6, min = 1, 
second max = 5, second min = 2, and 
so on... Modified array is : 6 1 5 2 4 3.
Example 2:
Input:
n = 11
arr[]={10,20,30,40,50,60,70,80,90,100,110}
Output:110 10 100 20 90 30 80 40 70 50 60
Explanation: Max element = 110, min = 10, 
second max = 100, second min = 20, and 
so on... Modified array is : 
110 10 100 20 90 30 80 40 70 50 60.
Your Task:
The task is to complete the function rearrange() which rearranges elements as explained above. Printing of the modified array will be handled by driver code.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 <= n <= 10^6
1 <= arr[i] <= 10^7

Difficulty: MEDIUM
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).

Starter code:
#User function Template for python3

class Solution:

    ##Complete this function

    #Function to rearrange  the array elements alternately.

    def rearrange(self,arr, n): 

        ##Your code here

Solutions:
class Solution:

	def rearrange(self, arr, n):
		n = len(arr)
		temp = [0] * n
		start = 0
		end = n - 1
		for i in range(n):
			if i % 2 == 0:
				temp[i] = arr[end]
				end -= 1
			else:
				temp[i] = arr[start]
				start += 1
		for i in range(n):
			arr[i] = temp[i]


class Solution:

	def rearrange(self, arr, n):
		fst = 0
		lst = n - 1
		maxi = arr[lst] + 1
		for i in range(n):
			if i % 2 == 0:
				arr[i] += arr[lst] % maxi * maxi
				lst -= 1
			else:
				arr[i] += arr[fst] % maxi * maxi
				fst += 1
		for i in range(n):
			arr[i] //= maxi


class Solution:

	def rearrange(self, arr, n):
		max = arr[-1] + 1
		max_ind = n - 1
		min_ind = 0
		for i in range(n):
			if i % 2 == 0:
				arr[i] = arr[max_ind] % max * max + arr[i]
				max_ind = max_ind - 1
			else:
				arr[i] = arr[min_ind] % max * max + arr[i]
				min_ind = min_ind + 1
		for i in range(n):
			arr[i] = arr[i] // max


class Solution:

	def rearrange(self, arr, n):
		max_element = arr[n - 1] + 1
		max_index = n - 1
		min_index = 0
		for i in range(n):
			if i % 2 == 0:
				arr[i] += arr[max_index] % max_element * max_element
				max_index -= 1
			else:
				arr[i] += arr[min_index] % max_element * max_element
				min_index += 1
		for i in range(n):
			arr[i] = arr[i] // max_element


class Solution:

	def rearrange(self, arr, n):
		maxi = max(arr) + 1
		mini = 0
		count = 0
		j = n - 1
		for i in range(n):
			if count % 2 == 0:
				arr[i] = arr[i] + arr[j] % maxi * maxi
				j -= 1
				count += 1
			elif count % 2 != 0:
				arr[i] = arr[i] + arr[mini] % maxi * maxi
				mini += 1
				count += 1
		for i in range(n):
			arr[i] = arr[i] // maxi
		return arr


class Solution:

	def rearrange(self, arr, n):
		lst = []
		c1 = n - 1
		c2 = 0
		for i in range(n):
			if i % 2 == 0:
				lst.append(arr[c1])
				c1 -= 1
			else:
				lst.append(arr[c2])
				c2 += 1
		arr.clear()
		arr.extend(lst)
		lst.clear()


class Solution:

	def rearrange(self, arr, n):
		maxi = n - 1
		mini = 0
		maxval = arr[maxi] + 1
		for i in range(n):
			if i % 2 == 0:
				arr[i] += arr[maxi] % maxval * maxval
				maxi -= 1
			else:
				arr[i] += arr[mini] % maxval * maxval
				mini += 1
		for i in range(n):
			arr[i] = arr[i] // maxval


class Solution:

	def rearrange(self, arr, n):
		max_indx = n - 1
		min_indx = 0
		max_ele = arr[n - 1] + 1
		for i in range(n):
			if i % 2 == 0:
				arr[i] += arr[max_indx] % max_ele * max_ele
				max_indx = max_indx - 1
			else:
				arr[i] += arr[min_indx] % max_ele * max_ele
				min_indx = min_indx + 1
		for i in range(n):
			arr[i] = arr[i] // max_ele


class Solution:

	def rearrange(self, arr, n):
		if n == 1:
			return arr[0]
		else:
			k = []
			i = 0
			j = n - 1
			while j >= i:
				k.append(arr[j])
				if i == j:
					break
				k.append(arr[i])
				i += 1
				j -= 1
			arr.clear()
			arr.extend(k)


class Solution:

	def rearrange(self, arr, n):
		max_idx = n - 1
		min_idx = 0
		max_elem = arr[n - 1] + 1
		for i in range(0, n):
			if i % 2 == 0:
				arr[i] += arr[max_idx] % max_elem * max_elem
				max_idx -= 1
			else:
				arr[i] += arr[min_idx] % max_elem * max_elem
				min_idx += 1
		for i in range(0, n):
			arr[i] = arr[i] // max_elem


class Solution:

	def rearrange(self, arr, n):
		i = 0
		j = n - 1
		answer = []
		while i <= j:
			answer.append(arr[j])
			answer.append(arr[i])
			j -= 1
			i += 1
		for i in range(n):
			arr[i] = answer[i]


class Solution:

	def rearrange(self, arr, n):
		o = len(arr)
		k = []
		v = len(arr) // 2
		if len(arr) == 1:
			k.append(arr[0])
		else:
			for i in range(v):
				k.append(arr[o - i - 1])
				k.append(arr[i])
			if o % 2 != 0:
				k.append(arr[v])
			arr.clear()
			arr.extend(k)


class Solution:

	def rearrange(self, arr, n):
		temp = n * [None]
		i = 0
		j = n - 1
		flag = True
		for k in range(n):
			if flag == True:
				temp[k] = arr[j]
				j -= 1
			else:
				temp[k] = arr[i]
				i += 1
			flag = bool(1 - flag)
		for i in range(n):
			arr[i] = temp[i]
		return arr


class Solution:

	def rearrange(self, arr, n):
		temp = n * [None]
		i = 0
		j = n - 1
		for k in range(n):
			if k % 2 == 0:
				temp[k] = arr[j]
				j -= 1
			else:
				temp[k] = arr[i]
				i += 1
		for i in range(n):
			arr[i] = temp[i]
		return arr


class Solution:

	def rearrange(self, arr, n):
		l = []
		i = 0
		j = n - 1
		while i < j:
			l.append(arr[j])
			l.append(arr[i])
			i += 1
			j -= 1
		if i == j:
			l.append(arr[i])
		arr.clear()
		for i in l:
			arr.append(i)


class Solution:

	def rearrange(self, arr, n):
		if len(arr) == 1:
			return
		l = 0
		r = n - 1
		arr2 = [0] * n
		c = 0
		while l <= r:
			arr2[c] = arr[r]
			if l != r:
				arr2[c + 1] = arr[l]
			c += 2
			l += 1
			r -= 1
		arr.clear()
		arr.extend(arr2)


class Solution:

	def rearrange(self, arr, n):
		initial_arr = [i for i in arr]
		left_ptr = 0
		right_ptr = n - 1
		cur_pos = 0
		while left_ptr <= right_ptr:
			arr[cur_pos] = initial_arr[right_ptr]
			cur_pos += 1
			if cur_pos < n:
				arr[cur_pos] = initial_arr[left_ptr]
				cur_pos += 1
			left_ptr += 1
			right_ptr -= 1


class Solution:

	def rearrange(self, arr, n):
		mx = arr[n - 1] + 1
		mn_idx = 0
		mx_idx = n - 1
		for i in range(0, n):
			if i % 2 == 0:
				arr[i] += arr[mx_idx] % mx * mx
				mx_idx -= 1
			else:
				arr[i] += arr[mn_idx] % mx * mx
				mn_idx += 1
		for i in range(0, n):
			arr[i] = arr[i] // mx


class Solution:

	def rearrange(self, arr, n):
		mini = 0
		maxi = n - 1
		temp = []
		for i in range(n):
			if i % 2 == 0:
				temp.append(arr[maxi])
				maxi -= 1
			else:
				temp.append(arr[mini])
				mini += 1
		arr.clear()
		arr.extend(temp)
		temp.clear()
		return arr


class Solution:

	def rearrange(self, a, n):
		x = a[-1] + 1
		j = n - 1
		z = 0
		for i in range(n):
			if i % 2 == 0:
				a[i] += a[j] % x * x
				j -= 1
			else:
				a[i] += a[z] % x * x
				z += 1
		for i in range(n):
			a[i] = a[i] // x


class Solution:

	def rearrange(self, arr, n):
		mi = 0
		ma = n - 1
		mx = arr[n - 1] + 1
		for i in range(n):
			if i % 2 != 0:
				arr[i] = arr[i] + arr[mi] % mx * mx
				mi += 1
			else:
				arr[i] = arr[i] + arr[ma] % mx * mx
				ma -= 1
		for i in range(n):
			arr[i] = int(arr[i] / mx)


class Solution:

	def rearrange(self, arr, n):
		l = []
		c = 0
		c1 = n - 1
		for i in range(n):
			if i % 2 == 0:
				l.append(arr[c1])
				c1 -= 1
			else:
				l.append(arr[c])
				c += 1
		arr.clear()
		arr.extend(l)
		l.clear()


class Solution:

	def rearrange(self, arr, n):
		i = 0
		j = n - 1
		ans = []
		right = True
		while i <= j:
			if right:
				ans.append(arr[j])
				right = False
				j -= 1
			else:
				ans.append(arr[i])
				right = True
				i += 1
		for i in range(n):
			arr[i] = ans[i]


class Solution:

	def rearrange(self, arr, n):
		i = 0
		min_ind = 0
		max_ind = n - 1
		creator = max(arr) + 1
		while i < n:
			if i & 1:
				arr[i] += arr[min_ind] % creator * creator
				min_ind += 1
			else:
				arr[i] += arr[max_ind] % creator * creator
				max_ind -= 1
			i += 1
		for i in range(len(arr)):
			arr[i] //= creator


class Solution:

	def rearrange(self, arr, n):
		i = 0
		j = n - 1
		max_num = arr[n - 1] + 1
		for k in range(n):
			if k % 2 == 0:
				arr[k] += arr[j] % max_num * max_num
				j -= 1
			else:
				arr[k] += arr[i] % max_num * max_num
				i += 1
		for i in range(n):
			arr[i] = int(arr[i] / max_num)


class Solution:

	def rearrange(self, arr, n):
		mx = arr[n - 1] + 1
		ls = 0
		ms = n - 1
		for i in range(n):
			if i % 2 == 0:
				arr[i] = int(arr[i] + arr[ms] % mx * mx)
				ms -= 1
			else:
				arr[i] = int(arr[i] + arr[ls] % mx * mx)
				ls += 1
		for i in range(n):
			arr[i] = int(arr[i] / mx)


class Solution:

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


class Solution:

	def rearrange(self, arr, n):
		lst = []
		s = n - 1
		i = 0
		while i < n // 2:
			lst += [arr[s]]
			lst += [arr[i]]
			s -= 1
			i += 1
		if n % 2 != 0:
			lst += [arr[n // 2]]
		arr[:] = lst[:]


class Solution:

	def rearrange(self, arr, n):
		i = 0
		j = n - 1
		b = []
		t = 1
		while i <= j:
			if t == 1:
				b.append(arr[j])
				j -= 1
			else:
				b.append(arr[i])
				i += 1
			t *= -1
		for i in range(n):
			arr[i] = b[i]


class Solution:

	def rearrange(self, arr, n):
		a = [False for i in range(n)]
		i = 0
		j = 1
		while j < n:
			a[j] = arr[i]
			i += 1
			j += 2
		i = n - 1
		j = 0
		while j < n:
			a[j] = arr[i]
			j += 2
			i -= 1
		for i in range(n):
			arr[i] = a[i]


class Solution:

	def rearrange(self, arr, n):
		i = j = 0
		result = arr.copy()
		arr.clear()
		end = n - 1
		start = 0
		for i in range(n):
			if i % 2 == 0:
				arr.append(result[end])
				end = end - 1
			else:
				arr.append(result[start])
				start = start + 1


class Solution:

	def rearrange(self, arr, n):
		maxi = arr[n - 1] + 1
		j = n - 1
		for i in range(0, n, 2):
			arr[i] += arr[j] % maxi * maxi
			j -= 1
		j = 0
		for i in range(1, n, 2):
			arr[i] += arr[j] % maxi * maxi
			j += 1
		for i in range(n):
			arr[i] = math.floor(arr[i] / maxi)


class Solution:

	def rearrange(self, arr, n):
		farr = arr.copy()
		arr.clear()
		(a, b) = (0, n - 1)
		while a <= b:
			if a == b:
				arr.append(farr[a])
			else:
				arr.append(farr[b])
				arr.append(farr[a])
			a += 1
			b -= 1


class Solution:

	def rearrange(self, arr, n):
		m = arr[n - 1] + 1
		l = 0
		r = n - 1
		flag = 0
		for i in range(n):
			if flag == 0:
				arr[i] = arr[i] + arr[r] % m * m
				r -= 1
			else:
				arr[i] = arr[i] + arr[l] % m * m
				l += 1
			flag = (flag + 1) % 2
		for i in range(n):
			arr[i] = arr[i] // m


class Solution:

	def rearrange(self, arr, n):
		l = [0] * n
		(i, j) = (0, n - 1)
		c = 0
		while i < j:
			l[c] = arr[j]
			c += 1
			l[c] = arr[i]
			c += 1
			j -= 1
			i += 1
		if n & 1:
			l[c] = arr[i]
		for i in range(n):
			arr[i] = l[i]


class Solution:

	def rearrange(self, arr, n):
		res = [None] * n
		s = 0
		l = n - 1
		l1 = []
		flag = True
		for i in range(n):
			if flag == True:
				l1.append(arr[l])
				l -= 1
			else:
				l1.append(arr[s])
				s += 1
			flag = 1 - bool(flag)
		for i in range(n):
			arr[i] = l1[i]


class Solution:

	def rearrange(self, arr, n):
		rearranged = []
		p1 = 0
		p2 = n - 1
		if n > 1:
			while p1 <= p2:
				if p1 == p2:
					rearranged.append(arr[p1])
				else:
					rearranged.append(arr[p2])
					rearranged.append(arr[p1])
				p1 = p1 + 1
				p2 = p2 - 1
			for i in range(n):
				arr[i] = rearranged[i]
		return rearranged


class Solution:

	def rearrange(self, arr, n):
		a = []
		arr.sort()
		a1 = []
		a2 = []
		a = arr
		a1 = a[:n // 2]
		a2 = a[n // 2:]
		a2.sort(reverse=True)
		k = j = 0
		for i in range(n):
			if i % 2 == 0:
				arr[i] = a2[j]
				j += 1
			else:
				arr[i] = a1[k]
				k += 1


class Solution:

	def rearrange(self, arr, n):
		max = arr[n - 1] + 1
		i = 0
		j = n - 1
		while i < j:
			arr[i] = arr[i] + max * arr[j]
			i = i + 1
			j = j - 1
		k = n - 1
		i = n // 2 - 1
		if n % 2 != 0:
			arr[k] = arr[n // 2]
			k = k - 1
		while i >= 0:
			arr[k] = arr[i] % max
			arr[k - 1] = arr[i] // max
			k = k - 2
			i = i - 1


class Solution:

	def rearrange(self, arr, n):
		l = []
		if n <= 1:
			return
		for i in range(0, len(arr) // 2):
			l.append(arr[len(arr) - i - 1])
			l.append(arr[i])
		if n % 2 != 0:
			l.append(arr[n // 2])
		arr[:] = l


class Solution:

	def rearrange(self, arr, n):
		m = arr.copy()
		k = -1
		for i in range(0, len(arr), 2):
			arr[i] = m[k]
			k -= 1
			l = 0
		for i in range(1, len(arr), 2):
			arr[i] = m[l]
			l += 1


class Solution:

	def rearrange(self, arr, n):
		temp = arr.copy()
		flag = -1
		(p, q) = (0, n - 1)
		for i in range(n):
			if flag == -1:
				arr[i] = temp[q]
				q -= 1
				flag = 1
			else:
				arr[i] = temp[p]
				p += 1
				flag = -1
		return arr


class Solution:

	def rearrange(self, arr, n):
		temp = [None] * n
		(l, r) = (0, n - 1)
		flag = True
		for i in range(n):
			if flag:
				temp[i] = arr[r]
				r -= 1
			else:
				temp[i] = arr[l]
				l += 1
			flag = not flag
		for i in range(n):
			arr[i] = temp[i]


class Solution:

	def rearrange(self, arr, n):
		arr.sort()
		m = arr.copy()
		(i, j) = (0, len(m) - 1)
		k = 0
		while k < n:
			arr[k] = m[j]
			k += 1
			j -= 1
			if k < n:
				arr[k] = m[i]
				i += 1
				k += 1
			else:
				break
		return arr


class Solution:

	def rearrange(self, a, n):
		x = a[n - 1] + 1
		j = n - 1
		for i in range(0, n, 2):
			a[i] = a[i] + a[j] % x * x
			j -= 1
		j = 0
		for i in range(1, n, 2):
			a[i] = a[i] + a[j] % x * x
			j += 1
		for i in range(n):
			a[i] = a[i] // x
		return a


class Solution:

	def rearrange(self, arr, n):
		if n == 1:
			return
		for i in range(0, n, 2):
			t = arr[i]
			if t < 0:
				continue
			for _ in range(n):
				j = 2 * i + 1
				if j >= n:
					j = 2 * (n - 1 - i)
				if arr[j] > 0:
					(arr[j], t) = (-t, arr[j])
					i = j
				else:
					break
		for i in range(n):
			arr[i] = -arr[i]


class Solution:

	def rearrange(self, A, n):
		min_idx = 0
		max_idx = n - 1
		maxi = A[n - 1] + 1
		for i in range(n):
			if i % 2 == 0:
				A[i] += A[max_idx] % maxi * maxi
				max_idx -= 1
			else:
				A[i] += A[min_idx] % maxi * maxi
				min_idx += 1
		for i in range(n):
			A[i] //= maxi
		return A


class Solution:

	def rearrange(self, arr, n):
		a = 0
		b = n - 1
		l = []
		for i in range(n):
			if i % 2 == 0:
				l.append(arr[b])
				b -= 1
			else:
				l.append(arr[a])
				a += 1
		arr.clear()
		arr.extend(l)
		l.clear()


class Solution:

	def rearrange(self, arr, n):
		ptr1 = 0
		ptr2 = n - 1
		ans = []
		i = 0
		while i < n / 2:
			ans.append(arr[ptr2])
			ans.append(arr[ptr1])
			i += 1
			ptr2 -= 1
			ptr1 += 1
		arr.clear()
		for i in ans:
			arr.append(i)
		if n % 2 != 0:
			arr.pop()


class Solution:

	def rearrange(self, arr, n):
		newarr = n * [None]
		flag = True
		s = 0
		l = n - 1
		for i in range(0, n):
			if flag == True:
				newarr[i] = arr[l]
				l -= 1
				flag = False
			else:
				newarr[i] = arr[s]
				s += 1
				flag = True
		for i in range(n):
			arr[i] = newarr[i]
		return arr


class Solution:

	def rearrange(self, arr, n):
		temp = n * [None]
		(small, large) = (0, n - 1)
		flag = True
		for i in range(n):
			if flag is True:
				temp[i] = arr[large]
				large -= 1
			else:
				temp[i] = arr[small]
				small += 1
			flag = bool(1 - flag)
		for i in range(n):
			arr[i] = temp[i]
		return arr


class Solution:

	def rearrange(self, arr, n):
		i = 0
		j = len(arr) - 1
		answer = []
		while i <= j:
			if len(answer) % 2:
				answer.append(arr[i])
				i = i + 1
			else:
				answer.append(arr[j])
				j = j - 1
		for i in range(n):
			arr[i] = answer[i]
		return arr


class Solution:

	def rearrange(self, arr, n):
		temp = [num for num in arr]
		left = 0
		right = n - 1
		i = 0
		while left <= right:
			if i == n:
				break
			arr[i] = temp[right]
			i += 1
			if i == n:
				break
			arr[i] = temp[left]
			i += 1
			left += 1
			right -= 1


class Solution:

	def rearrange(self, arr, n):
		pmin = 0
		pmax = n - 1
		divider = arr[-1] + 1
		for i in range(n):
			val_max = arr[pmax]
			val_min = arr[pmin]
			if i % 2 == 0:
				arr[i] += val_max % divider * divider
				pmax -= 1
			else:
				arr[i] += val_min % divider * divider
				pmin += 1
		for i in range(n):
			arr[i] = arr[i] // divider
		return arr


class Solution:

	def rearrange(self, arr, n):
		arr1 = arr[::-1]
		arr2 = arr
		i = 0
		j = 0
		k = 0
		ls = []
		while i < n:
			if i % 2 == 0:
				ls.append(arr1[j])
				j += 1
			elif i % 2 != 0:
				ls.append(arr2[k])
				k += 1
			i += 1
		for i in range(n):
			arr[i] = ls[i]
		return arr


class Solution:

	def rearrange(self, arr, n):
		i = 0
		j = n - 1
		flag = True
		m = max(arr) + 1
		for x in range(n):
			if flag:
				val = arr[j] % m
				arr[x] += m * val
				j -= 1
				flag = False
			else:
				val = arr[i] % m
				arr[x] += m * val
				i += 1
				flag = True
		for i in range(n):
			arr[i] //= m
		return arr


class Solution:

	def rearrange(self, A, n):
		max_i = n - 1
		min_i = 0
		max_val = A[n - 1] + 1
		for i in range(n):
			if i % 2 == 0:
				A[i] = A[i] + A[max_i] % max_val * max_val
				max_i = max_i - 1
			else:
				A[i] = A[i] + A[min_i] % max_val * max_val
				min_i = min_i + 1
		for i in range(n):
			A[i] = int(A[i] / max_val)


class Solution:

	def rearrange(self, arr, n):
		a = sorted(arr)
		(m, n) = (0, -1)
		list1 = []
		for i in range(len(arr)):
			if i % 2 == 0:
				arr[i] = a[n]
				n -= 1
			else:
				arr[i] = a[m]
				m += 1


class Solution:

	def rearrange(self, arr, n):
		mod = arr[n - 1] + 1
		l = 0
		r = n - 1
		for i in range(n):
			if i % 2 == 0:
				arr[i] = arr[r] % mod * mod + arr[i]
				r -= 1
			else:
				arr[i] = arr[l] % mod * mod + arr[i]
				l += 1
		for i in range(n):
			arr[i] //= mod
		return arr


class Solution:

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


class Solution:

	def rearrange(self, arr, n):
		a = []
		(i, j) = (0, n - 1)
		while i < j:
			a.append(arr[j])
			j -= 1
			a.append(arr[i])
			i += 1
		if n % 2 != 0:
			a.append(arr[i])
		arr.clear()
		arr[:] = a


class Solution:

	def rearrange(self, arr, n):
		new_arr = []
		left = 0
		right = n - 1
		for i in range(n):
			if i % 2 == 0:
				new_arr.append(arr[right])
				right -= 1
			else:
				new_arr.append(arr[left])
				left += 1
		arr[:] = new_arr[:]


class Solution:

	def rearrange(self, arr, n):
		max_elem = arr[n - 1] + 1
		even = 0
		odd = n - 1
		for i in range(n):
			if i % 2 == 0:
				arr[i] += arr[odd] % max_elem * max_elem
				odd -= 1
			else:
				arr[i] += arr[even] % max_elem * max_elem
				even += 1
		for i in range(n):
			arr[i] = arr[i] // max_elem


class Solution:

	def rearrange(self, arr, n):
		last = n - 1
		fir = 0
		mx = arr[n - 1] + 1
		for i in range(n):
			if i & 1:
				arr[i] += arr[fir] % mx * mx
				fir += 1
			else:
				arr[i] += arr[last] % mx * mx
				last -= 1
		for i in range(n):
			arr[i] //= mx


class Solution:

	def rearrange(self, arr, n):
		maxi = []
		mini = []
		for i in range(0, n // 2):
			mini.append(arr[i])
		for i in range(n - 1, n // 2 - 1, -1):
			maxi.append(arr[i])
		n = len(maxi)
		m = len(mini)
		i = 0
		l = []
		while i < n:
			l.append(maxi[i])
			if i < m:
				l.append(mini[i])
			i += 1
		n = len(arr)
		for i in range(n):
			arr[i] = l[i]


class Solution:

	def rearrange(self, arr, n):
		if n % 2 == 0:
			for i in range(n // 2):
				arr.append(arr[n - 1 - i])
				arr.append(arr[i])
		else:
			for i in range(n // 2):
				arr.append(arr[n - 1 - i])
				arr.append(arr[i])
			arr.append(arr[math.floor(n / 2)])
		arr[:] = arr[n:]
		return