Given a array of length N, at each step it is reduced by 1 element. In the first step the maximum element would be removed, while in the second step minimum element of the remaining array would be removed, in the third step again the maximum and so on. Continue this till the array contains only 1 element. And find the final element remaining in the array.
 
Example 1:
Input:
N = 7
A[] = {7, 8, 3, 4, 2, 9, 5}
Ouput:
5
Explanation:
In first step '9' would be removed, in 2nd step
'2' will be removed, in third step '8' will be
removed and so on. So the last remaining
element would be '5'.  
 
Example 2:
Input:
N = 8
A[] = {8, 1, 2, 9, 4, 3, 7, 5}
Ouput:
4
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function leftElement() which takes the array A[] and its size N as inputs and returns the final remaining element in the array.
Expected Time Complexity: O(NLogN)
Expected Auxiliary Space: O(1)
 
Constraints:
1 ≤ N ≤ 10^{6}
1 ≤ A_{i} ≤ 1000

Difficulty: EASY
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(NLogN)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3



class Solution:

    def leftElement(self, arr, n):

    # Your code goes here  

    



Solutions:
class Solution:

	def leftElement(self, arr, n):
		arr = sorted(arr)
		if n % 2 != 0:
			return arr[n // 2]
		elif n % 2 == 0:
			return arr[n // 2 - 1]


class Solution:

	def leftElement(self, arr, n):
		arr.sort()
		if n % 2 == 0:
			return arr[int(n / 2 - 1)]
		else:
			return arr[int(n / 2)]


class Solution:

	def leftElement(self, arr, n):
		r = sorted(arr)
		return r[n // 2 - 1] if n % 2 == 0 else r[n // 2]


class Solution:

	def leftElement(self, arr, n):
		l = []
		for i in arr:
			l.append(i)
		r = sorted(l)
		if len(r) % 2 == 0:
			val = int(len(r) / 2)
			return r[val - 1]
		elif len(r) == 1:
			return r[0]
		else:
			val = int(len(r) / 2)
			return r[val]


class Solution:

	def leftElement(self, a, n):
		a.sort()
		k = int(n / 2)
		if n % 2 != 0:
			return a[k]
		else:
			return a[k - 1]


import math

class Solution:

	def leftElement(self, arr, n):
		arr.sort()
		mid_index = math.ceil((n - 2) / 2)
		return arr[mid_index]


class Solution:

	def leftElement(self, arr, n):
		arr.sort()
		(start, end, choice) = (-1, n, 1)
		while end - start != 2:
			if choice == 1:
				end -= 1
				choice = 0
			else:
				start += 1
				choice = 1
		return arr[start + 1]


class Solution:

	def leftElement(self, arr, n):
		a = sorted(arr)
		i = int(n / 2)
		if n % 2 != 0:
			return a[i]
		else:
			return a[i - 1]


from array import *

class Solution:

	def leftElement(self, arr, n):
		arr.sort()
		if n % 2 != 0:
			return arr[n // 2]
		else:
			return arr[n // 2 - 1]


class Solution:

	def leftElement(self, arr, n):
		arr.sort()
		a = []
		if len(arr) % 2 == 0:
			even1 = int(len(arr) / 2)
			even2 = int(len(arr) / 2) - 1
			a.append(arr[even1])
			a.append(arr[even2])
			return min(a)
		else:
			odd = int(len(arr) / 2)
			return arr[odd]


class Solution:

	def leftElement(self, a, n):
		a.sort()
		if n % 2 == 1:
			return a[n // 2]
		return a[(n - 1) // 2]


class Solution:

	def leftElement(self, arr, n):
		arr.sort()
		return arr[(n - 1) // 2]


class Solution:

	def leftElement(self, arr, n):
		arr.sort()
		n = n - 1
		if n % 2 == 0:
			left = n // 2
			right = n // 2
		else:
			left = n // 2
			right = n // 2 + 1
		arr = arr[left:]
		return arr[0]


class Solution:

	def leftElement(self, arr, n):
		l = sorted(arr)
		if len(l) % 2 == 0:
			return l[len(l) // 2 - 1]
		elif len(l) % 2 != 0:
			return l[len(l) // 2]
		else:
			return l[0]


class Solution:

	def leftElement(self, arr, n):
		arr.sort()
		start = -1
		end = n
		oddeve = 0
		while start != end:
			if oddeve == 0:
				end -= 1
				oddeve += 1
			else:
				start += 1
				oddeve -= 1
		return arr[start]


class Solution:

	def leftElement(self, arr, n):
		arr.sort()
		if len(arr) % 2 == 0:
			m = len(arr) // 2
		else:
			m = (len(arr) + 1) // 2
		return arr[m - 1]


class Solution:

	def leftElement(self, arr, n):
		if not arr:
			return None
		if len(arr) == 1:
			return arr[0]
		arr.sort()
		n = len(arr)
		if n % 2 == 0:
			return arr[n // 2 - 1]
		else:
			return arr[n // 2]


class Solution:

	def leftElement(self, arr, n):
		s = sorted(arr)
		l = len(s)
		b = 0
		if l % 2 != 0:
			b = s[(l - 1) // 2]
			return b
		else:
			c = s[(l - 2) // 2]
			return c


class Solution:

	def leftElement(self, arr, n):
		A = sorted(arr)
		if n % 2 == 1:
			return A[(n + 1) // 2 - 1]
		else:
			return A[n // 2 - 1]


class Solution:

	def leftElement(self, arr, n):
		arr.sort()
		if n % 2 == 0:
			f = arr[n // 2 - 1]
			return f
		else:
			d = n // 2
			return arr[d]