Given an unsorted array of size N. Find the first element in array such that all of its left elements are smaller and all right elements to it are greater than it.
Note: Left and right side elements can be equal to required element. And extreme elements cannot be required element.
 
Example 1:
Input:
N = 4
A[] = {4, 2, 5, 7}
Output:
5
Explanation:
Elements on left of 5 are smaller than 5
and on right of it are greater than 5.
 
Example 2:
Input:
N = 3
A[] = {11, 9, 12}
Output:
-1
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function findElement() which takes the array A[] and its size N as inputs and returns the required element. If no such element present in array then return -1.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
 
Constraints:
3 <= N <= 10^{6}
1 <= A[i] <= 10^{6}

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

Starter code:
#User function Template for python3



def findElement( arr, n):

    

    

    



Solutions:
def findElement(arr, n):
	ans = -1
	maxi = arr[0]
	h = set()
	for i in range(1, n - 1):
		if arr[i] >= maxi:
			h.add(i)
			maxi = arr[i]
	mini = arr[-1]
	for i in range(n - 2, 0, -1):
		if i in h and arr[i] <= mini:
			ans = i
			mini = arr[i]
		if arr[i] < mini:
			mini = arr[i]
	if ans == -1:
		return -1
	return arr[ans]


def findElement(arr, n):
	ans = -1
	max = arr[0]
	for i in range(1, n):
		if arr[i] < max:
			ans = -1
		elif arr[i] >= max:
			if ans == -1 and i != n - 1:
				ans = arr[i]
			max = arr[i]
	return ans


def findElement(arr, n):
	l = len(arr)
	i = l - 2
	right_min = [0] * l
	right_min[l - 1] = arr[l - 1]
	while i >= 0:
		if arr[i] <= right_min[i + 1]:
			right_min[i] = arr[i]
		elif arr[i] > right_min[i + 1]:
			right_min[i] = right_min[i + 1]
		i -= 1
	i = 1
	left_max = arr[0]
	while i < l - 1:
		if arr[i] >= left_max:
			if arr[i] == right_min[i]:
				return arr[i]
			left_max = arr[i]
		i += 1
	return -1


def findElement(arr, n):
	arr1 = [arr[n - 1]]
	m = arr[n - 1]
	for i in range(n - 2, -1, -1):
		if arr[i] < m:
			arr1.append(arr[i])
			m = arr[i]
		else:
			arr1.append(m)
	arr1.reverse()
	m = arr[0]
	for i in range(1, n - 1):
		if arr[i] >= m and arr[i] <= arr1[i + 1]:
			return arr[i]
		if arr[i] > m:
			m = arr[i]
	return -1


def findElement(arr, n):
	maxi = arr[0]
	mini = arr[-1]
	ans1 = [1] * n
	ans2 = [1] * n
	for i in range(n):
		if arr[i] > maxi:
			maxi = arr[i]
		ans1[i] = maxi
	for i in range(n - 1, -1, -1):
		if arr[i] < mini:
			mini = arr[i]
		ans2[i] = mini
	for i in range(1, n - 1):
		if ans1[i] == ans2[i]:
			return ans1[i]
	else:
		return -1


def findElement(arr, n):
	flag = 0
	m = arr[0]
	if arr == sorted(arr):
		return arr[1]
	for i in range(n - 1):
		if m <= arr[i]:
			m = arr[i]
			flag = i
	for i in range(flag, n):
		if m > arr[i]:
			return -1
	if flag != 0:
		return m
	return -1


def findElement(arr, n):
	(max_left, min_right, max_l, min_r) = ([], [], float('-inf'), float('inf'))
	for i in range(0, n):
		(max_l, min_r) = (max(max_l, arr[i]), min(min_r, arr[n - 1 - i]))
		max_left.append(max_l)
		min_right.append(min_r)
	for i in range(1, n - 1):
		if max_left[i] <= arr[i] <= min_right[n - 1 - i]:
			return arr[i]
	return -1


def findElement(arr, n):
	arr2 = {}
	ele = -1
	max = arr[0]
	min = arr[n - 1]
	for i in range(1, n):
		if arr[i] >= max:
			max = arr[i]
			arr2[max] = 1
	for i in range(n - 2, -1, -1):
		if arr[i] <= min:
			min = arr[i]
			if min in arr2.keys():
				ele = arr[i]
	return ele


def findElement(arr, n):
	(arr1, arr2) = ([1] * n, [1] * n)
	maxi = arr[0]
	mini = arr[-1]
	for i in range(n):
		if arr[i] > maxi:
			maxi = arr[i]
		arr1[i] = maxi
	for i in range(n - 1, -1, -1):
		if arr[i] < mini:
			mini = arr[i]
		arr2[i] = mini
	for i in range(1, n - 1):
		if arr1[i] == arr2[i]:
			return arr1[i]
	else:
		return -1


def findElement(arr, n):
	(arr1, arr2) = ([1] * n, [1] * n)
	max = arr[0]
	min = arr[-1]
	for i in range(n):
		if arr[i] > max:
			max = arr[i]
		arr1[i] = max
	for i in range(n - 1, -1, -1):
		if arr[i] < min:
			min = arr[i]
		arr2[i] = min
	for i in range(1, n - 1):
		if arr1[i] == arr2[i]:
			return arr1[i]
	else:
		return -1


def findElement(arr, n):
	max_left = []
	min_right = []
	max_l = -1
	min_r = 100000000.0
	for i in range(0, n):
		max_l = max(max_l, arr[i])
		max_left.append(max_l)
	for i in range(len(arr) - 1, -1, -1):
		min_r = min(min_r, arr[i])
		min_right.append(min_r)
	min_right.reverse()
	for i in range(1, n - 1):
		if max_left[i] <= arr[i] and arr[i] <= min_right[i]:
			return arr[i]
	return -1


def findElement(a, n):

	def check(m):
		x = 0
		for i in range(m):
			if a[i] > a[m]:
				x = x + 1
				break
		if x == 0:
			return True

	def check1(m):
		x = 0
		for i in range(m + 1, n):
			if a[i] < a[m]:
				x = x + 1
				break
		if x == 0:
			return True
	y = 0
	for i in range(1, n - 1):
		if check(i) == True and check1(i) == True:
			return a[i]
			y = y + 1
			break
	if y == 0:
		return -1


def findElement(arr, n):
	(left_max, left_max_elem) = ([], float('-inf'))
	(right_min, right_min_elem) = ([], float('inf'))
	dict_ = {}
	for index in range(n):
		elem = arr[index]
		if arr[index] > left_max_elem:
			left_max_elem = elem
		if arr[-index - 1] < right_min_elem:
			right_min_elem = arr[-index - 1]
		left_max.append(left_max_elem)
		right_min.append(right_min_elem)
	for index in range(1, n - 1):
		left = left_max[index - 1] if index > 0 else float('inf')
		if left <= arr[index] <= right_min[-index - 1]:
			return arr[index]
	return -1


def check(arr, n, ind):
	i = ind - 1
	j = ind + 1
	while i >= 0:
		if arr[i] > arr[ind]:
			return False
		i -= 1
	while j < n:
		if arr[j] < arr[ind]:
			return False
		j += 1
	return True

def findElement(arr, n):
	for i in range(1, n - 1):
		if check(arr, n, i):
			return arr[i]
	return -1


def findElement(arr, n):
	maxi = []
	cur_max = arr[0]
	if n <= 2:
		return -1
	for i in range(n):
		if cur_max < arr[i]:
			cur_max = arr[i]
		maxi.append(cur_max)
	mini = []
	cur_min = arr[n - 1]
	for i in range(n - 1, -1, -1):
		if cur_min > arr[i]:
			cur_min = arr[i]
		mini.append(cur_min)
	mini.reverse()
	for i in range(1, n - 1):
		if arr[i] >= maxi[i] and arr[i] <= mini[i]:
			return arr[i]
	return -1


def findElement(arr, n):
	maxi = [arr[0]]
	mini = [arr[-1]]
	for i in range(1, n):
		maxi.append(max(maxi[-1], arr[i]))
	for i in range(n - 2, -1, -1):
		mini.insert(0, min(mini[0], arr[i]))
	for i in range(1, n - 1):
		if mini[i] == maxi[i]:
			return mini[i]
	return -1


def findElement(arr, n):
	max_arr = []
	maxi = arr[0]
	for i in range(n):
		if arr[i] > maxi:
			maxi = arr[i]
		max_arr.append(maxi)
	min_arr = []
	mini = arr[-1]
	for i in range(n - 1, -1, -1):
		if arr[i] < mini:
			mini = arr[i]
		min_arr.append(mini)
	min_arr.reverse()
	for i in range(1, n - 1):
		if min_arr[i] == max_arr[i]:
			return min_arr[i]
	else:
		return -1


def findElement(arr, n):
	for i in range(1, n - 1):
		curr = arr[i]
		left = i - 1
		right = i + 1
		while left > -1:
			if arr[left] <= curr:
				left -= 1
			else:
				break
		while right < n:
			if arr[right] >= curr:
				right += 1
			else:
				break
		if left == -1 and right == n:
			return curr
	else:
		return -1


def findElement(arr, n):
	max = []
	ele = arr[0]
	max.append(ele)
	for i in range(1, n):
		if arr[i] > ele:
			ele = arr[i]
		max.append(ele)
	min = []
	ele = arr[n - 1]
	min.append(ele)
	for i in range(n - 2, -1, -1):
		if arr[i] < ele:
			ele = arr[i]
		min.append(ele)
	min.reverse()
	for i in range(0, n):
		if i != 0 and i != n - 1 and (min[i] == max[i]):
			ele = min[i]
			return ele
	return -1


def findElement(arr, n):
	maxi = arr[0]
	for i in range(1, n - 1):
		maxi = max(maxi, arr[i])
		if maxi <= arr[i] and min(arr[i + 1:]) >= arr[i]:
			return arr[i]
	return -1


def findElement(arr, n):
	max_lv = arr[0]
	sol = -1
	for i in range(1, len(arr) - 1):
		if arr[i] >= max_lv:
			j = i + 1
			while j < n:
				if arr[i] <= arr[j]:
					j += 1
				else:
					break
			if j == n and i < n - 1:
				sol = arr[i]
				break
			else:
				max_lv = arr[i]
	return sol


def findElement(arr, n):
	right = [0] * n
	right[n - 1] = arr[n - 1]
	left = [0] * n
	left[0] = arr[0]
	m = n - 1
	for i in range(1, n):
		left[i] = max(left[i - 1], arr[i])
	for i in range(n - 2, -1, -1):
		right[i] = min(right[i + 1], arr[i])
	for i in range(1, n - 1):
		if arr[i] >= left[i] and arr[i] <= right[i]:
			return arr[i]
	return -1


def findElement(arr, n):
	L = [arr[0]]
	ele = arr[0]
	for i in range(1, n):
		if arr[i] > ele:
			ele = arr[i]
		L.append(ele)
	R = [arr[-1]]
	ele = arr[-1]
	for i in range(n - 2, -1, -1):
		if arr[i] < ele:
			ele = arr[i]
		R.append(ele)
	R.reverse()
	for i in range(1, n - 1):
		if arr[i] >= L[i] and arr[i] <= R[i]:
			return arr[i]
	return -1


def findElement(arr, n):
	mini = [arr[n - 1]]
	for i in range(n - 2, 1, -1):
		if mini[-1] >= arr[i]:
			mini.append(arr[i])
		else:
			mini.append(mini[-1])
	leftmaxi = arr[0]
	for i in range(1, n - 1):
		if leftmaxi <= arr[i] <= mini[-1]:
			return arr[i]
		mini.pop()
		leftmaxi = max(leftmaxi, arr[i])
	return -1


def leftRight(n, arr):
	left = [0] * n
	right = [0] * n
	left[0] = arr[0]
	right[n - 1] = arr[n - 1]
	for i in range(1, n):
		left[i] = max(left[i - 1], arr[i])
	for i in range(n - 1, 0, -1):
		right[i - 1] = min(right[i], arr[i - 1])
	for i in range(1, n - 1):
		(l, r) = (left[i - 1], right[i + 1])
		if arr[i] >= l and arr[i] <= r:
			return arr[i]
	return -1

def findElement(arr, n):
	return leftRight(n, arr)


def findElement(arr, n):
	leftMax = [None] * n
	leftMax[0] = arr[0]
	for i in range(1, n):
		leftMax[i] = max(leftMax[i - 1], arr[i])
	rightMin = [None] * n
	rightMin[n - 1] = arr[n - 1]
	for i in range(n - 2, -1, -1):
		rightMin[i] = min(rightMin[i + 1], arr[i])
	for i in range(1, n - 1):
		if leftMax[i - 1] <= arr[i] and arr[i] <= rightMin[i + 1]:
			return arr[i]
	return -1


def findElement(arr, n):
	maxarr = []
	minarr = []
	maxx = arr[0]
	minn = arr[n - 1]
	for i in range(1, n - 1):
		if arr[i] > maxx:
			maxx = arr[i]
		maxarr.append(maxx)
	for j in range(n - 1, 0, -1):
		if arr[j] < minn:
			minn = arr[j]
		minarr.insert(0, minn)
	for i in range(n - 2):
		if minarr[i] == maxarr[i]:
			return arr[i + 1]
	return -1


def findElement(arr, n):
	i = 1
	while i < n - 1:
		found = True
		for j in range(n):
			if j < i and arr[j] > arr[i]:
				found = False
				break
			if j > i and arr[j] < arr[i]:
				found = False
				break
		if found:
			return arr[i]
		i += 1
	return -1


def findElement(arr, n):
	big = arr[0]
	small = 9999999999999
	for i in range(1, n - 1):
		if arr[i] > big:
			big = arr[i]
	for i in range(1, n - 1):
		if arr[i] < small:
			small = arr[i]
	if small == arr[1] and small >= arr[0] and (small < arr[n - 1]):
		return small
	if big <= arr[n - 1] and big >= arr[0] and (big == arr[n - 2]):
		return big
	else:
		return -1


def findElement(arr, n):
	n = len(arr)
	l = [0] * n
	r = [0] * n
	max_e = arr[0]
	min_e = arr[-1]
	for i in range(n):
		if max_e < arr[i]:
			max_e = arr[i]
		l[i] = max_e
	for i in range(n - 1, -1, -1):
		if min_e > arr[i]:
			min_e = arr[i]
		r[i] = min_e
	for i in range(1, n - 1):
		if arr[i] >= l[i - 1] and arr[i] <= r[i + 1]:
			return arr[i]
	return -1


def findElement(arr, n):
	for i in range(1, n - 1):
		j = i - 1
		k = i + 1
		flag = True
		while j >= 0:
			if arr[i] < arr[j]:
				flag = False
				break
			j -= 1
		while flag and k < n:
			if arr[k] < arr[i]:
				flag = False
				break
			k += 1
		if flag:
			return arr[i]
	return -1


def findElement(arr, n):
	l = []
	r = []
	ml = -3
	mr = 100000000.0
	for i in range(0, n):
		ml = max(ml, arr[i])
		l.append(ml)
	for i in range(len(arr) - 1, -1, -1):
		mr = min(mr, arr[i])
		r.append(mr)
	r.reverse()
	for i in range(1, n - 1):
		if l[i] <= arr[i] and arr[i] <= r[i]:
			return arr[i]
	return -1


from collections import defaultdict

def findElement(arr, n):
	dec = defaultdict(int)
	right_min = arr[n - 1]
	for i in range(n - 2, -1, -1):
		if arr[i] <= right_min:
			dec[arr[i], i] += 1
			right_min = arr[i]
	left_max = arr[0]
	for i in range(1, n - 1):
		if arr[i] >= left_max:
			dec[arr[i], i] += 1
			left_max = arr[i]
			if dec[arr[i], i] == 2:
				return arr[i]
	return -1


def findElement(arr, n):
	ret = False
	maxima = arr[0]
	if n < 3:
		return -1
	for i in range(1, n):
		if arr[i] >= maxima:
			if not ret and i != n - 1:
				maxima = arr[i]
				ret = True
		else:
			ret = False
	if ret:
		return maxima
	else:
		return -1


def findElement(arr, n):
	nsl = [-1]
	st = [arr[0]]
	for i in range(1, len(arr)):
		while st and st[-1] <= arr[i]:
			st.pop()
		if len(st) == 0:
			nsl.append(1)
		else:
			nsl.append(-1)
		st.append(arr[i])
	a = arr.copy()
	a.reverse()
	nsr = [-1]
	st1 = [a[0]]
	for i in range(1, len(a)):
		while st1 and st1[-1] >= a[i]:
			st1.pop()
		if len(st1) == 0:
			nsr.append(1)
		else:
			nsr.append(-1)
		st1.append(a[i])
	nsr.reverse()
	for i in range(len(arr)):
		if nsl[i] == 1 and nsr[i] == 1:
			return arr[i]
	return -1


def findElement(arr, n):
	left_max_arr = []
	left_max = -99999999
	for i in range(n):
		if arr[i] >= left_max:
			left_max = arr[i]
		left_max_arr.append(left_max)
	right_min = 99999999
	right_min_arr = []
	for i in range(n):
		if arr[n - i - 1] <= right_min:
			right_min = arr[n - i - 1]
		right_min_arr.append(right_min)
	for i in range(1, n - 1):
		if arr[i] >= left_max_arr[i] and arr[i] <= right_min_arr[n - i - 1]:
			return arr[i]
	return -1


def findElement(arr, n):
	for i in range(1, n - 1):
		c = True
		m = i
		while i > 0:
			if arr[m] >= arr[i - 1]:
				i -= 1
			else:
				c = False
				break
		if c == False:
			continue
		else:
			i = m
			while i < n - 1:
				if arr[m] <= arr[i + 1]:
					i += 1
				else:
					c = False
					break
		if c == True:
			return arr[m]
	return -1


def findElement(arr, n):
	(l, t) = ([arr[0]], [arr[n - 1]])
	for i in range(1, n):
		l.append(max(arr[i], l[-1]))
	for i in range(n - 2, -1, -1):
		t.append(min(arr[i], t[-1]))
	t = t[::-1]
	for i in range(1, n - 1):
		if arr[i] == l[i] and arr[i] == t[i]:
			return arr[i]
	return -1


def findElement(arr, n):
	max_so_far = []
	min_so_far = [0] * n
	curmax = 0
	curmin = 100001
	if n == 0:
		return -1
	for i in range(n):
		if arr[i] > curmax:
			curmax = arr[i]
		max_so_far.append(curmax)
	for i in range(n):
		if arr[n - i - 1] < curmin:
			curmin = arr[n - i - 1]
		min_so_far[n - i - 1] = curmin
	for i in range(n):
		if arr[i] >= max_so_far[i] and arr[i] <= min_so_far[i] and (i != 0) and (i != n - 1):
			return arr[i]
	return -1


def findElement(arr, n):
	small_flag = 0
	big_flag = 0
	for i in range(n):
		for j in range(i):
			if arr[j] > arr[i]:
				small_flag = 1
				break
		for k in range(i + 1, n):
			if arr[k] < arr[i]:
				big_flag = 1
				break
		if small_flag == 0 and big_flag == 0 and (i != n - 1) and (i != 0):
			return arr[i]
		else:
			small_flag = 0
			big_flag = 0
	return -1


def findElement(arr, n):
	leftmax = []
	rightmin = []
	mx = arr[0]
	j = 0
	while j < n:
		if mx < arr[j]:
			mx = arr[j]
		j += 1
		leftmax.append(mx)
	j = -1
	mn = arr[-1]
	while j >= -n:
		if arr[j] < mn:
			mn = arr[j]
		j -= 1
		rightmin.append(mn)
	j = 1
	rightmin = rightmin[::-1]
	if arr[0] >= leftmax[1] and arr[0] <= rightmin[1]:
		return arr[0]
	while j < n - 1:
		if arr[j] >= leftmax[j - 1] and arr[j] <= rightmin[j + 1]:
			return arr[j]
		j += 1
	return -1


import copy

def findElement(arr, n):
	left_max = [0] * n
	right_min = [0] * n
	left_max[0] = arr[0]
	right_min[n - 1] = arr[n - 1]
	for i in range(1, n):
		left_max[i] = max(left_max[i - 1], arr[i])
	for i in range(n - 2, -1, -1):
		right_min[i] = min(right_min[i + 1], arr[i])
	for i in range(1, n - 1):
		if arr[i] >= left_max[i] and arr[i] <= right_min[i]:
			return arr[i]
	return -1


def findElement(arr, n):
	left = [0] * n
	right = [0] * n
	left[0] = arr[0]
	mini = arr[0]
	for i in range(1, n):
		if arr[i] > mini:
			mini = arr[i]
		left[i] = mini
	right[-1] = arr[-1]
	mini = arr[-1]
	for i in range(n - 2, -1, -1):
		if arr[i] < mini:
			mini = arr[i]
		right[i] = mini
	for i in range(1, n - 1):
		if left[i] == right[i]:
			return arr[i]
	return -1


def findElement(arr, n):
	for i in range(1, n - 1):
		l = i - 1
		r = i + 1
		flag = True
		while l >= 0:
			if arr[i] < arr[l]:
				flag = False
				break
			l -= 1
		while r <= n - 1:
			if arr[i] > arr[r]:
				flag = False
				break
			r += 1
		if flag:
			return arr[i]
	return -1


def findElement(arr, n):
	b = [0] * n
	c = [0] * n
	b[0] = 0
	c[n - 1] = 0
	l = arr[0]
	for i in range(1, n):
		if arr[i - 1] > l:
			l = arr[i - 1]
		b[i] = l
	s = arr[n - 1]
	for i in range(n - 2, -1, -1):
		if arr[i + 1] < s:
			s = arr[i + 1]
		c[i] = s
	flag = 0
	for i in range(n):
		if arr[i] >= b[i] and arr[i] <= c[i] and (i != 0):
			return arr[i]
			flag = 1
	if flag == 0:
		return -1