There are N buildings in Linear Land. They appear in a linear line one after the other and their heights are given in the array arr[]. Geek wants to select three buildings in Linear Land and remodel them as recreational spots. The third of the selected building must be taller than the first and shorter than the second.
Can geek build the three-building recreational zone? 
Example 1:
Input:
N = 6
arr[] = {4, 7, 11, 5, 13, 2}
Output:
True
Explanation:
[4, 7, 5] fits the condition. 
Example 2:
Input:
N = 4
arr[] = {11, 11, 12, 9}
Output:
False
Explanation:
No 3 buildings fit the given condition. 
Your Task:
You don't need to read input or print anything. Complete the function recreationalSpot() which takes the array arr[] and its size N as input parameters and returns a boolean value based on whether his building selection was successful or not.
Note: The generated output will be "True" or "False".
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{4}
1 ≤ arr[i] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Data structures

Starter code: #User function Template for python3

class Solution:
	def recreationalSpot(self, arr, n):
		# Your code goes here 

Solutions:
class Solution:

	def recreationalSpot(self, arr, n):
		k = -10 ** 9
		s = []
		for i in range(n - 1, -1, -1):
			if arr[i] < k:
				return True
			else:
				while len(s) != 0 and arr[i] > s[-1]:
					k = s[-1]
					s.pop()
			s.append(arr[i])
		return False


class Solution:

	def recreationalSpot(self, arr, n):
		stack = []
		currmin = arr[0]
		for i in arr[1:]:
			while stack and i >= stack[-1][0]:
				stack.pop()
			if stack and i > stack[-1][1]:
				return True
			stack.append([i, currmin])
			currmin = min(i, currmin)
		return False


class Solution:

	def recreationalSpot(self, arr, n):
		a = []
		b = []
		for i in arr:
			if a == []:
				a = [i]
			elif i < a[-1]:
				a.append(i)
			else:
				a.append(a[-1])
		for i in arr:
			if b == []:
				b = [i]
			elif i > b[-1]:
				b.append(i)
			else:
				b.append(b[-1])
		arr = arr[::-1]
		a = a[::-1]
		b = b[::-1]
		for i in range(n - 2):
			if arr[i] > a[i + 2] and arr[i] < b[i + 1]:
				return True
		return False


class Solution:

	def recreationalSpot(self, arr, n):
		if n < 3:
			return False
		pre_min = [arr[0]]
		for i in range(1, n):
			pre_min.append(min(arr[i], pre_min[-1]))
		(stack, top) = ([], -1)
		for i in range(n - 1, -1, -1):
			if arr[i] > pre_min[i]:
				while top >= 0 and stack[-1] <= pre_min[i]:
					stack.pop(-1)
					top -= 1
				if top >= 0 and stack[-1] < arr[i]:
					return True
				stack.append(arr[i])
				top += 1
		return False


class Solution:

	def recreationalSpot(self, arr, N):
		if N < 3:
			return False
		preMin = [0] * N
		preMin[0] = arr[0]
		for i in range(1, N):
			preMin[i] = min(preMin[i - 1], arr[i])
		stack = []
		for j in range(N - 1, -1, -1):
			if arr[j] > preMin[j]:
				while len(stack) > 0 and stack[-1] <= preMin[j]:
					del stack[-1]
				if len(stack) > 0 and stack[-1] < arr[j]:
					return True
				stack.append(arr[j])
		return False


class Solution:

	def recreationalSpot(self, arr, n):
		mi = -1
		s = []
		for a in reversed(arr):
			if a < mi:
				return True
			while len(s) > 0 and s[-1] < a:
				mi = s[-1]
				s.pop()
			s.append(a)
		return False


class Solution:

	def recreationalSpot(self, a, n):
		ar = []
		ar.append(-1)
		m = a[0]
		for i in range(1, n):
			if a[i] > m:
				ar.append(m)
			else:
				ar.append(-1)
				m = a[i]
		stk = []
		res = []
		for i in range(n - 1, -1, -1):
			if ar[i] != -1:
				while len(stk) > 0 and (a[i] <= stk[-1] or ar[i] >= stk[-1]):
					stk.pop()
				if len(stk) == 0:
					res.append(-1)
				else:
					return 1
				stk.append(a[i])
			else:
				stk.append(a[i])
		return 0


class Solution:

	def recreationalSpot(self, arr, n):
		mini = float('inf')
		stack = []
		for item in arr:
			while stack and item >= stack[-1][1]:
				stack.pop()
			if stack and item > stack[-1][0]:
				return True
			mini = min(mini, item)
			stack.append((mini, item))
		return False


class Solution:

	def recreationalSpot(self, arr, n):
		stack = [[arr[0], arr[0]]]
		for item in arr:
			if item < stack[-1][0]:
				stack.append([item, item])
				continue
			if item > stack[-1][1]:
				stack[-1][1] = item
				while len(stack) > 1 and stack[-1][1] >= stack[-2][1]:
					stack.pop(-2)
			for (short, tall) in stack:
				if short < item < tall:
					return True
		return False


from collections import deque

class Solution:

	def recreationalSpot(self, arr, n):
		stack = [[arr[0], arr[0]]]
		for item in arr:
			for pair in stack:
				if item > pair[0] and item < pair[1]:
					return True
			if item < stack[-1][0]:
				stack.append([item, item])
			elif item > stack[-1][1]:
				stack[-1][1] = item
				while len(stack) < 1 and stack[-1][0] <= stack[-2][0] and (stack[-1][1] >= stack[-2[0]]):
					stack.pop(-2)
		return False


class Solution:

	def recreationalSpot(self, arr, n):
		third = float('-inf')
		st = []
		for i in range(n - 1, -1, -1):
			if arr[i] < third:
				return True
			else:
				while st and arr[i] > st[-1]:
					third = st.pop()
			st.append(arr[i])
		return False


class Solution:

	def recreationalSpot(self, arr, n):
		a = arr.copy()
		for i in range(1, n):
			a[i] = min(a[i], a[i - 1])
		s = []
		for i in range(n - 1, 0, -1):
			while s and arr[i] > s[-1]:
				if a[i - 1] < s[-1]:
					return True
				s.pop()
			s.append(arr[i])
		return False


class Solution:

	def recreationalSpot(self, nums, n):
		stack = []
		last = 0
		for i in range(n - 1, -1, -1):
			if nums[i] < last:
				return True
			while len(stack) > 0 and nums[i] > stack[len(stack) - 1]:
				last = stack.pop()
			stack.append(nums[i])
		return False


class Solution:

	def recreationalSpot(self, A, N):
		prefmin = [0] * N
		prefmin[0] = A[0]
		for i in range(1, N):
			prefmin[i] = min(prefmin[i - 1], A[i])
		stk = [A[-1]]
		for i in range(N - 2, 0, -1):
			if A[i] > prefmin[i]:
				while stk and stk[-1] <= prefmin[i]:
					stk.pop()
				if stk and stk[-1] < A[i]:
					return True
				stk.append(A[i])
		return False


class Solution:

	def recreationalSpot(self, arr, n):
		x = []
		x.append(arr[0])
		for i in arr[1:]:
			x.append(min(i, x[-1]))
		y = []
		for i in range(n - 1, -1, -1):
			while len(y) > 0 and y[-1] <= x[i]:
				y.pop()
			if len(y) > 0 and arr[i] > y[-1]:
				return True
			y.append(arr[i])
		return False


class Solution:

	def recreationalSpot(self, arr, n):
		stack = []
		curMin = arr[0]
		stack.append([arr[0], curMin])
		for ele in arr[1:]:
			while stack and stack[-1][0] <= ele:
				stack.pop()
			if stack and stack[-1][0] > ele and (ele > stack[-1][1]):
				return True
			stack.append([ele, curMin])
			curMin = min(curMin, ele)
		return False


class Solution:

	def recreationalSpot(self, arr, n):
		mini = [2 ** 31 for i in range(n)]
		for i in range(1, n):
			mini[i] = min(mini[i - 1], arr[i - 1])
		maxi = [-1 for i in range(n)]
		stack = []
		for i in range(n - 1, -1, -1):
			if not stack:
				stack.append(arr[i])
				continue
			else:
				while stack and stack[-1] <= mini[i]:
					stack.pop()
				if stack and stack[-1] < arr[i]:
					return True
			stack.append(arr[i])
		return False


class Solution:

	def recreationalSpot(self, arr, n):
		smallest_left = []
		mini = arr[0]
		for i in range(n):
			if arr[i] <= mini:
				mini = arr[i]
				smallest_left.append(-1)
			else:
				smallest_left.append(mini)
		st = []
		for i in range(n - 1, 0, -1):
			while st and st[-1] <= smallest_left[i]:
				st.pop()
			if len(st) > 0 and smallest_left[i] != -1 and (st[-1] < arr[i]):
				return True
			st.append(arr[i])
		return False


class Solution:

	def recreationalSpot(self, arr, n):
		mini = [10 ** 9] * n
		mini[0] = arr[0]
		for i in range(1, n):
			mini[i] = min(mini[i - 1], arr[i])
		s = []
		for i in range(n - 1, 0, -1):
			if len(s) == 0:
				s.append(arr[i])
				continue
			while len(s) > 0 and s[-1] <= mini[i - 1]:
				s.pop()
			if len(s) > 0 and mini[i - 1] < arr[i] and (s[-1] < arr[i]):
				return 1
			s.append(arr[i])
		return 0


class Solution:

	def recreationalSpot(self, arr, n):
		if n < 3:
			return False
		stack = []
		minSofar = [arr[0]]
		for i in range(1, n):
			minSofar.append(min(minSofar[i - 1], arr[i]))
		for i in range(n - 1, 0, -1):
			while stack and arr[i] > stack[-1]:
				if minSofar[i - 1] < stack[-1]:
					return True
				stack.pop()
			stack.append(arr[i])
		return False
if __name__ == '__main__':
	tcs = int(input())
	for _ in range(tcs):
		n = int(input())
		arr = [int(x) for x in input().split()]
		ob = Solution()
		if ob.recreationalSpot(arr, n):
			print('True')
		else:
			print('False')


class Solution:

	def recreationalSpot(self, arr, n):
		mn = [0] * n
		mn[0] = arr[0]
		for i in range(1, n):
			mn[i] = min(mn[i - 1], arr[i])
		st = []
		for i in range(n - 1, -1, -1):
			if arr[i] != mn[i]:
				while st and st[-1] <= mn[i]:
					st.pop()
				if st and st[-1] < arr[i]:
					return True
			if not st:
				st.append(arr[i])
			elif arr[i] < st[-1]:
				st.append(arr[i])
		return False
if __name__ == '__main__':
	tcs = int(input())
	for _ in range(tcs):
		n = int(input())
		arr = [int(x) for x in input().split()]
		ob = Solution()
		if ob.recreationalSpot(arr, n):
			print('True')
		else:
			print('False')


class Solution:

	def recreationalSpot(self, l, n):
		l = l[::-1]
		s = []
		ak = -float('inf')
		for i in l:
			if i < ak:
				return True
			else:
				while s and s[-1] < i:
					ak = s.pop(-1)
			s.append(i)
		return False


inf = 100000

class Solution:

	def recreationalSpot(self, a, n):
		pm = [0 for i in range(n)]
		pm[0] = a[0]
		for i in range(1, n):
			if a[i] < pm[i - 1]:
				pm[i] = a[i]
			else:
				pm[i] = pm[i - 1]
		s = []
		key = 0
		for i in range(n - 1, 0, -1):
			if len(s) == 0:
				s.append(a[i])
				continue
			else:
				while s[-1] <= pm[i - 1]:
					s.pop()
					if len(s) == 0:
						break
				if len(s) == 0:
					s.append(a[i])
					continue
				if a[i] > s[-1]:
					key = 1
					break
				else:
					s.append(a[i])
		return key


class Solution:

	def recreationalSpot(self, arr, n):
		prefix_min = [-1] * n
		mi = arr[0]
		prefix_min[0] = arr[0]
		for i in range(1, n):
			prefix_min[i] = min(arr[i], prefix_min[i - 1])
		st = []
		j = n - 1
		while j:
			if prefix_min[j] < arr[j]:
				first = prefix_min[j]
				second = arr[j]
				while st and first >= st[-1]:
					st.pop()
				if st:
					if second > st[-1]:
						return True
			st.append(arr[j])
			j -= 1
		return False


def nextSmallerElement(arr, n):
	stack = []
	i = n - 1
	res = [n + 1 for _ in range(n)]
	while i >= 0:
		if len(stack) != 0:
			while len(stack) != 0 and stack[-1] >= arr[i]:
				stack.pop()
		res[i] = n + 1 if len(stack) == 0 else stack[-1]
		stack.append(arr[i])
		i -= 1
	return res

def prevSmallerElement(arr, n):
	stack = []
	i = 0
	res = [-1 for _ in range(n)]
	while i < n:
		if len(stack) != 0:
			while len(stack) != 0 and stack[-1] >= arr[i]:
				stack.pop()
		res[i] = -1 if len(stack) == 0 else stack[-1]
		stack.append(arr[i])
		i += 1
	return res

class Solution:

	def recreationalSpot(self, arr, n):
		if n < 3:
			return False
		premin = [0 for _ in range(n)]
		premin[0] = arr[0]
		for i in range(1, n):
			premin[i] = min(premin[i - 1], arr[i])
		stack = []
		for i in range(n - 1, -1, -1):
			if arr[i] > premin[i]:
				while len(stack) != 0 and premin[i] >= stack[-1]:
					stack.pop()
				if len(stack) != 0 and arr[i] > stack[-1]:
					return True
				stack.append(arr[i])
		return False


def nextSmallerElement(arr, n):
	stack = []
	i = n - 1
	res = [n + 1 for _ in range(n)]
	while i >= 0:
		if len(stack) != 0:
			while len(stack) != 0 and stack[-1] >= arr[i]:
				stack.pop()
		res[i] = n + 1 if len(stack) == 0 else stack[-1]
		stack.append(arr[i])
		i -= 1
	return res

def prevSmallerElement(arr, n):
	stack = []
	i = 0
	res = [-1 for _ in range(n)]
	while i < n:
		if len(stack) != 0:
			while len(stack) != 0 and stack[-1] >= arr[i]:
				stack.pop()
		res[i] = -1 if len(stack) == 0 else stack[-1]
		stack.append(arr[i])
		i += 1
	return res

class Solution:

	def recreationalSpot(self, arr, N):
		if N < 3:
			return 'No'
		preMin = [0] * N
		preMin[0] = arr[0]
		for i in range(1, N):
			preMin[i] = min(preMin[i - 1], arr[i])
		stack = []
		for j in range(N - 1, -1, -1):
			if arr[j] > preMin[j]:
				while len(stack) > 0 and stack[-1] <= preMin[j]:
					del stack[-1]
				if len(stack) > 0 and stack[-1] < arr[j]:
					return True
				stack.append(arr[j])
		return False


from collections import deque

class Solution:

	def recreationalSpot(self, arr, n):
		min_num = [-1] * n
		min_num[0] = arr[0]
		for i in range(1, n):
			min_num[i] = min(min_num[i - 1], arr[i])
		stk = deque()
		for j in range(n - 1, -1, -1):
			if arr[j] > min_num[j]:
				while stk and stk[len(stk) - 1] <= min_num[j]:
					stk.pop()
				if stk and stk[len(stk) - 1] < arr[j]:
					return True
				stk.append(arr[j])
		return False


class Solution:

	def recreationalSpot(self, arr, n):
		import sys
		second = -sys.maxsize
		stack = []
		sl = 0
		for i in range(n - 1, -1, -1):
			v = arr[i]
			if v < second:
				return True
			while sl > 0 and stack[sl - 1] < v:
				second = stack.pop()
				sl -= 1
			stack.append(v)
			sl += 1
		return False


class Solution:

	def recreationalSpot(self, arr, n):
		import sys
		nums = arr
		second = -sys.maxsize
		stack = []
		for num in reversed(nums):
			if num < second:
				return True
			while stack and stack[-1] < num:
				second = stack.pop()
			stack.append(num)
		return False


class Solution:

	def recreationalSpot(self, arr, n):
		nums = arr
		second = float('-inf')
		stack = []
		for num in reversed(nums):
			if num < second:
				return True
			while stack and stack[-1] < num:
				second = stack.pop()
			stack.append(num)
		return False


class Solution:

	def recreationalSpot(self, arr, n):
		min_arr = []
		min_arr.append(arr[0])
		for i in range(1, n):
			if min_arr[-1] < arr[i]:
				min_arr.append(min_arr[-1])
			else:
				min_arr.append(arr[i])
		st = []
		flag = False
		st.append(arr[n - 1])
		for j in range(n - 2, 0, -1):
			while len(st) > 0 and min_arr[j] >= st[-1]:
				st.pop()
			if len(st) > 0:
				if arr[j] > st[-1]:
					flag = True
					break
			st.append(arr[j])
		return flag


class Solution:

	def recreationalSpot(self, arr, n):
		if n < 3:
			return -1
		premin = [0] * n
		premin[0] = arr[0]
		for ind in range(1, n):
			premin[ind] = min(premin[ind - 1], arr[ind])
		stack = []
		for ind in range(n - 1, -1, -1):
			if arr[ind] > premin[ind]:
				while stack and stack[-1] <= premin[ind]:
					stack.pop()
				if stack and stack[-1] < arr[ind]:
					return 1
				stack.append(arr[ind])
		return 0


from collections import deque

class Solution:

	def recreationalSpot(self, arr, n):
		if n < 3:
			return False
		left_min = [0] * n
		min_ele = arr[0]
		for i in range(1, n):
			left_min[i] = min_ele
			min_ele = min(min_ele, arr[i])
		stack = deque()
		stack.append(arr[-1])
		for i in range(n - 2, 0, -1):
			l_ele = left_min[i]
			if l_ele >= arr[i]:
				continue
			while stack and stack[-1] <= l_ele:
				stack.pop()
			if stack and stack[-1] < arr[i]:
				return True
			if arr[i] > l_ele:
				stack.append(arr[i])
		return False


from math import inf

class Solution:

	def recreationalSpot(self, x, n):
		st = []
		el = -inf
		for i in range(n - 1, -1, -1):
			if x[i] < el:
				return True
			while st and x[i] > st[-1]:
				el = st.pop(-1)
			st.append(x[i])
		return False


class Solution:

	def recreationalSpot(self, nums, n):
		if len(nums) < 3:
			return False
		stack = []
		second = float('-inf')
		c = 0
		for i in range(len(nums) - 1, -1, -1):
			if nums[i] < second:
				return True
			while stack and stack[-1] < nums[i]:
				second = stack.pop()
			stack.append(nums[i])
		return False


class Solution:

	def recreationalSpot(self, nums, n):
		if len(set(nums)) < 3:
			return False
		min_nums = [nums[0]]
		for i in range(1, len(nums)):
			min_nums.append(min(nums[i], min_nums[-1]))
		stack = []
		i = len(nums) - 1
		for i in range(len(nums) - 1, -1, -1):
			if nums[i] > min_nums[i]:
				while stack and stack[-1] <= min_nums[i]:
					stack.pop()
				if stack and min_nums[i] < stack[-1] < nums[i]:
					return True
				stack.append(nums[i])
		return False


class Solution:

	def recreationalSpot(self, arr, n):
		if n < 3:
			return False
		preMin = [0] * n
		preMin[0] = arr[0]
		for i in range(1, n):
			preMin[i] = min(arr[i], preMin[i - 1])
		st = []
		for i in range(n - 1, -1, -1):
			if arr[i] > preMin[i]:
				while st and st[-1] <= preMin[i]:
					st.pop()
				if st and st[-1] < arr[i]:
					return True
				st.append(arr[i])
		return False


class Solution:

	def recreationalSpot(self, arr, n):
		k = -100000000000.0
		stack = []
		for i in range(n - 1, -1, -1):
			if arr[i] < k:
				return True
			else:
				while stack and arr[i] > stack[-1]:
					k = stack[-1]
					stack.pop()
			stack.append(arr[i])
		return False


class Solution:

	def recreationalSpot(self, arr, n):
		st = []
		m = -1000000000.0
		for i in arr[::-1]:
			if i < m:
				return True
			while st and st[-1] < i:
				m = st.pop()
			st.append(i)
		return False


def find132(arr):
	m = arr[0]
	mini = []
	for i in arr:
		m = min(i, m)
		mini.append(m)
	st = []
	for i in range(len(arr) - 1, -1, -1):
		while len(st) > 0 and mini[i] >= st[-1]:
			st.pop()
		if len(st) > 0 and arr[i] > st[-1]:
			return True
		st.append(arr[i])
	return False

class Solution:

	def recreationalSpot(self, arr, n):
		return find132(arr)


class Solution:

	def recreationalSpot(self, arr, n):
		third = -(1 << 31)
		stack = []
		for (i, elem) in enumerate(arr[::-1]):
			if elem < third:
				return True
			while stack and stack[-1] < elem:
				third = stack.pop()
			stack.append(elem)
		return False


class Solution:

	def recreationalSpot(self, arr, n):
		if n < 3:
			return False
		ma = []
		mn = 99999999999
		for i in arr:
			if i < mn:
				mn = i
			ma.append(mn)
		s = []
		c = n
		for i in arr[n - 1:0:-1]:
			c -= 1
			while s and s[-1] <= ma[c - 1]:
				s.pop()
			if s and i > s[-1]:
				return True
			s.append(i)
		return False


class Solution:

	def recreationalSpot(self, arr, n):
		st = []
		minleft = [0] * n
		minleft[0] = arr[0]
		minleft.append(float('inf'))
		for i in range(1, n):
			minleft[i] = min(minleft[i - 1], arr[i])
		st = []
		for j in range(n - 1, -1, -1):
			if arr[j] > minleft[j]:
				while st and st[-1] <= minleft[j]:
					st.pop()
				if st and st[-1] < arr[j]:
					return True
				st.append(arr[j])
		return False


def one_three_two_pattern(nums):
	n = len(nums)
	min_ = [None] * n
	min_[0] = nums[0]
	for i in range(1, n):
		min_[i] = min(min_[i - 1], nums[i])
	st = list()
	found = False
	for j in range(n - 1, -1, -1):
		while len(st) > 0 and st[-1] <= min_[j]:
			st.pop()
		if len(st) > 0 and st[-1] < nums[j]:
			found = True
			break
		st.append(nums[j])
	return found

class Solution:

	def recreationalSpot(self, arr, n):
		return one_three_two_pattern(arr)


class Solution:

	def recreationalSpot(self, arr, n):
		rightS = [n] * n
		rightL = [n] * n
		for i in range(n - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				rightS[i] = i + 1
			else:
				ni = rightS[i + 1]
				while ni != n and arr[i] <= arr[ni]:
					ni = rightS[ni]
				rightS[i] = ni
		for i in range(n - 2, -1, -1):
			if arr[i] < arr[i + 1]:
				rightL[i] = i + 1
			else:
				ni = rightL[i + 1]
				while ni != n and arr[i] >= arr[ni]:
					ni = rightL[ni]
				rightL[i] = ni
		lastone = 0
		for one in range(n - 2):
			if arr[one] <= arr[lastone]:
				lastone = one
				two = rightL[one]
				while two != n:
					three = rightS[two]
					while three != n:
						if arr[three] > arr[one]:
							if arr[two] > arr[three]:
								return True
							else:
								break
						three = rightL[three]
					two = rightL[two]
		return False


class Solution:

	def recreationalSpot(self, nums, n):
		stack = []
		s3 = float('-inf')
		for n in nums[::-1]:
			if n < s3:
				return True
			while stack and stack[-1] < n:
				s3 = stack.pop()
			stack.append(n)
		return False


class Solution:

	def recreationalSpot(self, arr, n):
		stack = []
		if len(arr) <= 2:
			return False
		if len(arr) == 3:
			if arr[0] < arr[2] < arr[1]:
				return True
			else:
				return False
		if arr[0] < arr[2] < arr[1]:
			return True
		temp = [float('inf')] * n
		for i in range(n):
			temp[i] = min(temp[i - 1], arr[i])
		for i in range(n - 1, -1, -1):
			if arr[i] > temp[i]:
				while stack and stack[-1] <= temp[i]:
					stack.pop()
				if stack and stack[-1] < arr[i]:
					return True
				stack.append(arr[i])
		return False


class Solution:

	def recreationalSpot(self, arr, n):
		stack = list()
		preMin = [arr[0]]
		for i in range(1, n):
			preMin.append(min(arr[i], preMin[i - 1]))
		for i in range(n - 1, 0, -1):
			if arr[i] > preMin[i]:
				while len(stack) > 0 and stack[len(stack) - 1] <= preMin[i]:
					th = stack.pop()
				if len(stack) > 0 and stack[len(stack) - 1] < arr[i]:
					return True
			stack.append(arr[i])
		return False


import math

class Solution:

	def recreationalSpot(self, arr, n):
		l = []
		if len(arr) <= 2:
			return False
		if len(arr) == 3:
			if arr[0] < arr[2] < arr[1]:
				return True
			else:
				return False
		if arr[0] < arr[2] < arr[1]:
			return True
		temp = [math.inf] * n
		for i in range(n):
			temp[i] = min(temp[i - 1], arr[i])
		for i in range(n - 1, -1, -1):
			if arr[i] > temp[i]:
				while l and l[-1] <= temp[i]:
					l.pop()
				if l and l[-1] < arr[i]:
					return True
				l.append(arr[i])
		return False


class Solution:

	def recreationalSpot(self, arr, n):
		temp = [0 for i in range(0, n)]
		temp[0] = arr[0]
		for i in range(1, n):
			temp[i] = min(temp[i - 1], arr[i])
		return self.utilFunc(temp, arr, n)

	def utilFunc(self, temp, arr, n):
		stack = []
		for i in range(n - 1, -1, -1):
			while len(stack) > 0 and temp[i] >= stack[-1]:
				stack.pop()
			if len(stack) > 0 and temp[i] < arr[i] and (arr[i] > stack[-1]):
				return True
			stack.append(arr[i])
		return False


class Solution:

	def recreationalSpot(self, arr, n):
		mins = []
		for i in range(len(arr)):
			if i == 0:
				mins.append(arr[i])
			else:
				mins.append(min(mins[-1], arr[i]))
		greaters = []
		for j in range(len(arr) - 1, -1, -1):
			while greaters and arr[greaters[-1]] <= mins[j]:
				greaters.pop()
			if greaters and arr[greaters[-1]] < arr[j]:
				return True
			greaters.append(j)
		return False


class Solution:

	def recreationalSpot(self, arr, n):
		small = [arr[0]]
		big = [float('-inf')]
		smallest = arr[0]
		biggest = float('-inf')
		for value in arr[1:]:
			if value >= biggest:
				biggest = value
				big = [value]
				small = [smallest]
			if value < smallest:
				smallest = value
				small.append(value)
				big.append(float('-inf'))
			for edge in range(len(small)):
				if value > small[edge] and value < big[edge]:
					return True
				if value > small[edge]:
					big[edge] = value
		return False


class Solution:

	def recreationalSpot(self, arr, n):
		from collections import deque
		stack = deque()
		third = -1000000007
		for i in arr[::-1]:
			if i < third:
				return True
			else:
				while stack and stack[-1] < i:
					third = stack.pop()
				stack.append(i)
		return False