Given an array A of N integers, find any 3 elements in it such that A[i] < A[j] < A[k] and i < j < k. 
Example 1:
Input:
N = 5
A[] = {1,2,1,1,3}
Output: 1
Explanation: a sub-sequence 1 2 3 exist.
Example 2:
Input:
N = 3
A[] = {1,1,3}
Output: 0
Explanation: no such sub-sequence exist.
Your Task:
Your task is to complete the function find3Numbers which finds any 3 elements in it such that A[i] < A[j] < A[k] and i < j < k. You need to return them as a vector/ArrayList/array (depending on the language cpp/Java/Python), if no such element is present then return the empty vector of size 0.
Note: The output will be 1 if the sub-sequence returned by the function is present in array A or else 0. If the sub-sequence returned by the function is not in the format as mentioned then the output will be -1.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 <= N <= 10^{5}
1 <= A[i] <= 10^{6}, for each valid i

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3







class Solution:

    def find3number(self,A, n):

        # code here

Solutions:
class Solution:

	def find3number(self, A, n):
		mina = [-1] * n
		maxa = [-1] * n
		min_ = 0
		max_ = n - 1
		for i in range(1, n):
			if arr[i] <= arr[min_]:
				mina[i] = -1
				min_ = i
			else:
				mina[i] = min_
		for i in range(n - 2, -1, -1):
			if arr[i] >= arr[max_]:
				maxa[i] = -1
				max_ = i
			else:
				maxa[i] = max_
		res = []
		for i in range(n):
			if mina[i] != -1 and maxa[i] != -1:
				res.append(arr[mina[i]])
				res.append(arr[i])
				res.append(arr[maxa[i]])
				return res
		return []


class Solution:

	def find3number(self, A, n):
		min_ = 0
		max_v = n - 1
		min_val = [] * n
		max_val = [0] * n
		q = []
		if n < 3:
			return q
		a = 10000000
		b = 0
		for i in range(n):
			if a > A[i]:
				a = A[i]
			min_val.append(a)
		for k in range(n - 1, -1, -1):
			if b < A[k]:
				b = A[k]
			max_val[k] = b
		for j in range(n):
			if min_val[j] < A[j] and A[j] < max_val[j]:
				q.append(min_val[j])
				q.append(A[j])
				q.append(max_val[j])
				return q
		return q


class Solution:

	def find3number(self, A, n):
		max = n - 1
		min = 0
		small = [0] * n
		small[0] = -1
		for i in range(1, n):
			if arr[i] <= arr[min]:
				min = i
				small[i] = -1
			else:
				small[i] = min
		great = [0] * n
		great[n - 1] = -1
		for i in range(n - 2, -1, -1):
			if arr[i] >= arr[max]:
				max = i
				great[i] = -1
			else:
				great[i] = max
		lis = []
		for i in range(n):
			if small[i] != -1 and great[i] != -1:
				lis.append(A[small[i]])
				lis.append(A[i])
				lis.append(A[great[i]])
				return lis
		return lis


class Solution:

	def find3number(self, a, n):
		left = []
		right = []
		left.append(a[0])
		smallest = a[0]
		right.append(a[n - 1])
		largest = a[n - 1]
		for i in range(n):
			if a[i] < smallest:
				smallest = a[i]
			left.append(smallest)
		for i in range(n - 1, -1, -1):
			if a[i] > largest:
				largest = a[i]
			right.append(largest)
		right.reverse()
		for i in range(n):
			if left[i] < a[i] and right[i] > a[i]:
				ans = []
				ans.append(left[i])
				ans.append(a[i])
				ans.append(right[i])
				return ans
		ans = []
		return ans


class Solution:

	def find3number(self, A, n):
		min_num = 0
		max_num = n - 1
		min_val = [] * n
		max_val = [0] * n
		q = []
		if n < 3:
			return q
		a = 10000000000
		b = 0
		for i in range(n):
			if a > A[i]:
				a = A[i]
			min_val.append(a)
		for k in range(n - 1, -1, -1):
			if b < A[k]:
				b = A[k]
			max_val[k] = b
		for j in range(n):
			if min_val[j] < A[j] and A[j] < max_val[j]:
				q.append(min_val[j])
				q.append(A[j])
				q.append(max_val[j])
				return q
		return q


class Solution:

	def find3number(self, A, N):
		min_val = arr[0]
		r = [0] * n
		r[n - 1] = arr[n - 1]
		for i in range(n - 2, -1, -1):
			r[i] = max(r[i + 1], arr[i])
		for i in range(1, n - 1):
			if arr[i] > min_val and arr[i] < r[i + 1]:
				return [min_val, arr[i], r[i + 1]]
			else:
				min_val = min(min_val, arr[i])
		return []


class Solution:

	def find3number(self, arr, n):
		maxi = n - 1
		mini = 0
		smaller = [0] * (n + 1)
		smaller[0] = -1
		for i in range(1, n):
			if arr[i] <= arr[mini]:
				mini = i
				smaller[i] = -1
			else:
				smaller[i] = mini
		greater = [0] * (n + 1)
		greater[n - 1] = -1
		for i in range(n - 2, -1, -1):
			if arr[i] >= arr[maxi]:
				maxi = i
				greater[i] = -1
			else:
				greater[i] = maxi
		for i in range(n):
			if smaller[i] != -1 and greater[i] != -1:
				return [arr[smaller[i]], arr[i], arr[greater[i]]]
		return []


class Solution:

	def find3number(self, a, n):
		(f, s, t, tmp) = (-1, -1, -1, -1)
		idx = 0
		for i in range(0, n - 1):
			if arr[i + 1] > arr[i]:
				f = arr[i]
				s = arr[i + 1]
				if i + 1 == n - 1:
					return []
				else:
					idx = i + 2
				break
		if f == s == -1:
			return []
		for i in range(idx, n):
			if arr[i] > s:
				t = arr[i]
				return [f, s, t]
				break
			elif tmp > -1 and arr[i] > tmp and (arr[i] <= s):
				if f < tmp:
					return [f, tmp, arr[i]]
				f = tmp
				s = arr[i]
				tmp = -1
			elif tmp > -1 and arr[i] < tmp:
				tmp = arr[i]
			else:
				tmp = arr[i]
		return []


class Solution:

	def find3number(self, A, n):
		a = A[0]
		second = float('inf')
		third = a
		for i in range(1, n):
			if A[i] < a:
				a = A[i]
			elif A[i] > a and A[i] < second:
				(second, third) = (A[i], a)
			elif A[i] > second:
				return [third, second, A[i]]
		return []


class Solution:

	def find3number(self, A, n):
		smallest_peak = None
		(i, j) = (None, None)
		for s in range(n - 1):
			if A[s + 1] > A[s]:
				if smallest_peak is None:
					smallest_peak = A[s + 1]
					i = s
					j = s + 1
				elif A[s + 1] < smallest_peak:
					smallest_peak = A[s + 1]
					i = s
					j = s + 1
				elif A[s + 1] > smallest_peak:
					return [A[i], A[j], A[s + 1]]
		return []


class Solution:

	def find3number(self, A, n):
		sm = 0
		lg = n - 1
		sma = [0] * n
		sma[0] = -1
		for i in range(1, n):
			if A[i] <= A[sm]:
				sm = i
				sma[i] = -1
			else:
				sma[i] = sm
		lag = [0] * n
		lag[n - 1] = -1
		for i in range(n - 2, -1, -1):
			if A[i] >= A[lg]:
				lg = i
				lag[i] = -1
			else:
				lag[i] = lg
		for i in range(n):
			if sma[i] != -1 and lag[i] != -1:
				return [A[sma[i]], A[i], A[lag[i]]]
		return []


class Solution:

	def find3number(self, A, n):
		st = []
		st_len = 0
		for i in range(n - 1, -1, -1):
			while st and st[-1] <= arr[i]:
				st.pop()
				st_len -= 1
			st.append(arr[i])
			st_len += 1
			if st_len == 3:
				return st[::-1]
		return []


class Solution:

	def find3number(self, arr, n):
		if n < 3:
			return []
		left = [arr[0]]
		curr_min = arr[0]
		curr_max = arr[n - 1]
		st_len = 0
		for i in range(1, n):
			curr_min = min(curr_min, arr[i])
			left.append(curr_min)
		for i in range(n - 2, 0, -1):
			if arr[i] > left[i - 1] and arr[i] < curr_max:
				return [left[i - 1], arr[i], curr_max]
			curr_max = max(curr_max, arr[i])
		return []


class Solution:

	def find3number(self, A, n):
		min = 0
		max = n - 1
		minA = [-1] * n
		maxA = [-1] * n
		ans = []
		for i in range(1, n):
			if A[i] <= A[min]:
				minA[i] = -1
				min = i
			else:
				minA[i] = min
		for i in range(n - 2, -1, -1):
			if A[i] >= A[max]:
				maxA[i] = -1
				max = i
			else:
				maxA[i] = max
		for i in range(0, n):
			if minA[i] != -1 and maxA[i] != -1:
				ans.append(A[minA[i]])
				ans.append(A[i])
				ans.append(A[maxA[i]])
				break
		return ans


class Solution:

	def find3number(self, a, n):
		l = [0] * n
		latest_min = l[0]
		for i in range(1, n):
			if a[i] <= a[latest_min]:
				l[i] = i
				latest_min = i
			else:
				l[i] = latest_min
		r = [n - 1] * n
		lastest_max = r[n - 1]
		for j in range(n - 2, -1, -1):
			if a[j] >= a[lastest_max]:
				r[j] = j
				lastest_max = j
			else:
				r[j] = lastest_max
		for i in range(n):
			if l[i] != i and r[i] != i:
				return [a[l[i]], a[i], a[r[i]]]
		return []


class Solution:

	def find3number(self, A, n):
		lnum = [0] * n
		rnum = [0] * n
		lnum[0] = A[0]
		rnum[n - 1] = A[n - 1]
		for i in range(1, n):
			lnum[i] = min(lnum[i - 1], A[i])
		for i in range(n - 2, -1, -1):
			rnum[i] = max(rnum[i + 1], A[i])
		for i in range(1, n - 1):
			if lnum[i] < A[i] and A[i] < rnum[i]:
				return (lnum[i], A[i], rnum[i])
		return []


class Solution:

	def find3number(self, nums, n):
		first = second = float('inf')
		seqlen = 0
		extrafirst = float('inf')
		for num in nums:
			if num <= first:
				extrafirst = first
				first = num
				seqlen = 1
			elif num <= second:
				second = num
				seqlen = 2
			elif seqlen == 2:
				return [first, second, num]
			else:
				return [extrafirst, second, num]
		return []


class Solution:

	def find3number(self, A, n):
		l = []
		for i in A[::-1]:
			if len(l) == 0:
				l.append(i)
				continue
			while len(l) > 0 and l[len(l) - 1] <= i:
				l.pop()
			l.append(i)
			if len(l) > 2:
				return l[::-1]
		return []


class Solution:

	def find3number(self, arr, n):
		first = second = -1
		minidx = 0
		for i in range(1, n):
			if arr[i] <= arr[minidx]:
				minidx = i
			elif second == -1:
				first = minidx
				second = i
			elif arr[i] <= arr[second]:
				second = i
				first = minidx
			else:
				return (arr[first], arr[second], arr[i])
		return []


class Solution:

	def find3number(self, A, n):
		a = A[0]
		b = 9999999
		m = a
		for i in range(1, n):
			if A[i] < a:
				a = A[i]
			elif A[i] < b and A[i] > a:
				b = A[i]
				m = a
			elif A[i] > b:
				return [m, b, A[i]]
		return []


class Solution:

	def find3number(self, a, n):
		lm = [] * n
		rm = [0] * n
		hv = float('inf')
		lv = float('-inf')
		for i in range(n):
			if hv > a[i]:
				hv = a[i]
			lm.append(hv)
		for i in range(n - 1, -1, -1):
			if lv < a[i]:
				lv = a[i]
			rm[i] = lv
		ans = []
		for i in range(n):
			if lm[i] < a[i] and rm[i] > a[i]:
				ans.append(lm[i])
				ans.append(a[i])
				ans.append(rm[i])
				return ans
		return ans


class Solution:

	def find3number(self, A, n):
		leftMin = [0] * n
		leftMin[0] = A[0]
		for i in range(1, n):
			leftMin[i] = min(leftMin[i - 1], A[i])
		rightMax = [0] * n
		rightMax[-1] = A[-1]
		for i in range(n - 2, -1, -1):
			rightMax[i] = max(rightMax[i + 1], A[i])
		for i in range(n):
			if leftMin[i] < A[i] and rightMax[i] > A[i]:
				return (leftMin[i], A[i], rightMax[i])
		return []


class Solution:

	def find3number(self, A, n):
		m_stack = []
		for i in A[::-1]:
			if m_stack and i < m_stack[-1]:
				m_stack.append(i)
			else:
				while m_stack and i >= m_stack[-1]:
					m_stack.pop()
				m_stack.append(i)
			if len(m_stack) == 3:
				return m_stack[::-1]
		return []


class Solution:

	def find3number(self, A, n):
		first = float('inf')
		second = float('inf')
		store_min = float('inf')
		for i in range(n):
			if A[i] <= first:
				first = A[i]
			elif A[i] <= second:
				second = A[i]
				store_min = first
			else:
				return [store_min, second, A[i]]
		return []


class Solution:

	def find3number(self, A, n):
		arr = [(A[0], [A[0]])]
		for item in A:
			if item > arr[-1][0]:
				arr.append((item, arr[-1][1] + [item]))
				if len(arr) > 2:
					return arr[-1][1]
			elif item <= arr[0][0]:
				arr[0] = (item, [item])
			elif len(arr) == 2 and item < arr[1][0]:
				arr[1] = (item, arr[0][1] + [item])
		return []


class Solution:

	def find3number(self, A, n):
		if len(A) >= 3:
			start = A[0]
			mid = None
			end = None
			i = 1
			while i < n - 1:
				if mid is None:
					mid = A[i]
				elif start < A[i] < mid:
					mid = A[i]
				if end is None:
					end = A[i + 1]
				if start < mid < end:
					return [start, mid, end]
				elif start > mid:
					start = mid
					mid = None
					if start < end:
						mid = end
					else:
						start = end
					end = None
				elif start == mid:
					mid = None
					end = None
				elif start < mid:
					if start > end:
						count = 0
						for j in range(i, n):
							if mid < A[j]:
								end = A[j]
								break
							if end < A[j]:
								count += 1
							if count >= 2:
								start = end
								end = None
								mid = None
								break
						else:
							end = None
					elif mid >= end:
						end = None
				i += 1
		return []


class Solution:

	def find3number(self, a, n):
		max = n - 1
		min = 0
		smaller = [0] * n
		smaller[0] = -1
		for i in range(1, n):
			if arr[i] <= arr[min]:
				min = i
				smaller[i] = -1
			else:
				smaller[i] = min
		greater = [0] * n
		greater[n - 1] = -1
		for i in range(n - 2, -1, -1):
			if arr[i] >= arr[max]:
				max = i
				greater[i] = -1
			else:
				greater[i] = max
		lis = []
		for i in range(0, n):
			if smaller[i] != -1 and greater[i] != -1:
				lis.append(a[smaller[i]])
				lis.append(a[i])
				lis.append(a[greater[i]])
				return lis
		return lis


class Solution:

	def find3number(self, A, n):
		prefix = [A[0]]
		suffix = [0 for i in range(n)]
		suffix[n - 1] = A[-1]
		ans = []
		for i in range(1, n):
			prefix.append(min(A[i], prefix[-1]))
			suffix[n - i - 1] = max(A[n - i - 1], suffix[n - i])
		for i in range(n):
			if prefix[i] < A[i] and suffix[i] > A[i]:
				return [prefix[i], A[i], suffix[i]]
		return ans


class Solution:

	def find3number(self, A, n):
		first = float('inf')
		second = float('inf')
		lis = []
		prevFirst = first
		for num in A:
			if num <= first:
				first = num
			elif num <= second:
				second = num
				prevFirst = first
			elif num > second:
				lis.append(prevFirst)
				lis.append(second)
				lis.append(num)
				return lis
		return lis


class Solution:

	def find3number(self, A, n):
		a = A[0]
		b = 1000000.0 + 1
		mn = a
		for i in range(1, n):
			if A[i] < a:
				a = A[i]
			elif A[i] < b and A[i] > a:
				b = A[i]
				mn = a
			elif A[i] > b:
				return [mn, b, A[i]]
		return []


class Solution:

	def find3number(self, A, n):
		smaller = [0] * 10000
		greater = [0] * 10000
		smaller[0] = -1
		greater[n - 1] = -1
		ans = []
		maxi = n - 1
		mini = 0
		for i in range(1, n):
			if A[i] <= A[mini]:
				mini = i
				smaller[i] = -1
			else:
				smaller[i] = mini
		for j in range(n - 2, -1, -1):
			if A[j] >= A[maxi]:
				maxi = j
				greater[j] = -1
			else:
				greater[j] = maxi
		for i in range(0, n):
			if smaller[i] != -1 and greater[i] != -1:
				ans.append(A[smaller[i]])
				ans.append(A[i])
				ans.append(A[greater[i]])
				break
		return ans


class Solution:

	def find3number(self, A, n):
		(i, j, k) = (A[0], sys.maxsize - 1, A[0])
		for val in A[1:]:
			if val < i:
				i = val
			elif val > i and val < j:
				j = val
				k = i
			elif val > j:
				return [k, j, val]
		return []


import sys

class Solution:

	def find3number(self, A, n):
		arr = A
		max = n - 1
		min = 0
		smaller = [0] * n
		smaller[0] = -1
		greater = [0] * n
		greater[n - 1] = -1
		for i in range(1, n):
			if arr[i] <= arr[min]:
				min = i
				smaller[i] = -1
			else:
				smaller[i] = min
		for j in range(n - 2, -1, -1):
			if arr[j] >= arr[max]:
				max = j
				greater[j] = -1
			else:
				greater[j] = max
		for i in range(n):
			if smaller[i] != -1 and greater[i] != -1:
				return [arr[smaller[i]], arr[i], arr[greater[i]]]
		return []


class Solution:

	def find3number(self, arr, n):
		res = []
		if n < 3:
			return res
		left = [0] * n
		left[0] = arr[0]
		for i in range(1, n):
			left[i] = min(left[i - 1], arr[i])
		right = [0] * n
		right[n - 1] = arr[n - 1]
		for i in range(n - 2, -1, -1):
			right[i] = max(right[i + 1], arr[i])
		for j in range(n):
			if left[j] < arr[j] and arr[j] < right[j]:
				return [left[j], arr[j], right[j]]
		return res


class Solution:

	def find3number(self, A, n):
		min = A[0]
		ans = []
		for i in range(1, n):
			if arr[i] > min:
				if ans != [] and arr[i] > ans[-1]:
					ans.append(arr[i])
					return ans
				else:
					ans = [min, arr[i]]
			else:
				min = arr[i]
		return []


class Solution:

	def find3number(self, arr, n):
		l1 = []
		l2 = []
		l3 = []
		l1.append(arr[0])
		l2.append(arr[n - 1])
		j = 0
		for i in range(1, n):
			l1.append(min(l1[i - 1], arr[i]))
		for i in range(n - 2, -1, -1):
			l2.append(max(l2[j], arr[i]))
			j += 1
		l2.reverse()
		for i in range(1, n - 1):
			if l1[i - 1] < arr[i] and arr[i] < l2[i + 1]:
				l3.append(l1[i - 1])
				l3.append(arr[i])
				l3.append(l2[i + 1])
				return l3
		return l3


class Solution:

	def find3number(self, A, n):
		min_arr = [-1] * n
		minimum = A[0]
		min_index = 0
		for i in range(1, n):
			element = A[i]
			if minimum < element:
				min_arr[i] = min_index
			elif minimum > element:
				minimum = element
				min_index = i
		maximum = A[n - 1]
		max_index = n - 1
		max_arr = [-1] * n
		for i in range(n - 2, -1, -1):
			element = A[i]
			if maximum > element:
				max_arr[i] = max_index
			elif maximum < element:
				maximum = element
				max_index = i
		for i in range(n):
			if min_arr[i] != -1 and max_arr[i] != -1:
				return [A[min_arr[i]], A[i], A[max_arr[i]]]
		return []


class Solution:

	def find3number(self, a, n):
		l = [0] * n
		latest_min = l[0]
		for i in range(1, n):
			if arr[i] <= arr[latest_min]:
				l[i] = i
				latest_min = i
			else:
				l[i] = latest_min
		r = [n - 1] * n
		latest_max = r[n - 1]
		for j in range(n - 1, -1, -1):
			if arr[j] >= arr[latest_max]:
				r[j] = j
				latest_max = j
			else:
				r[j] = latest_max
		for i in range(n):
			if l[i] != i and r[i] != i:
				return [arr[l[i]], arr[i], arr[r[i]]]
		return []


class Solution:

	def find3number(self, A, n):
		mina = [-1] * n
		maxa = [-1] * n
		mi = A[0]
		for i in range(1, n):
			if A[i] > mi:
				mina[i] = mi
			elif A[i] < mi:
				mi = A[i]
		mi = A[n - 1]
		for i in range(n - 2, -1, -1):
			if A[i] < mi:
				maxa[i] = mi
			elif A[i] > mi:
				mi = A[i]
		ans = []
		for i in range(n):
			(x, y, z) = (mina[i], A[i], maxa[i])
			if x == -1 or z == -1:
				continue
			if x < y < z:
				ans = [x, y, z]
				break
		return ans


class Solution:

	def find3number(self, A, n):
		if n < 3:
			return []
		minn1 = A[0]
		minn2 = None
		st_minn = A[0]
		count = 1
		maxx = None
		for i in range(1, n):
			if A[i] < minn1 and count == 1:
				minn1 = A[i]
				st_minn = A[i]
			elif A[i] > minn1 and count == 1:
				minn2 = A[i]
				count += 1
			elif count == 2 and A[i] < minn2 and (A[i] > minn1):
				minn2 = A[i]
			elif count == 2 and A[i] < st_minn:
				st_minn = A[i]
			if A[i] > st_minn and A[i] < minn2:
				minn1 = st_minn
				minn2 = A[i]
			elif minn2 and A[i] > minn2:
				maxx = A[i]
				break
		if maxx:
			return [minn1, minn2, maxx]
		else:
			return []


class Solution:

	def find3number(self, A, n):
		sm = [0] * n
		lr = [0] * n
		lr[-1] = A[-1]
		sm[0] = A[0]
		for i in range(n - 2, -1, -1):
			lr[i] = max(A[i], lr[i + 1])
		for i in range(1, n):
			sm[i] = min(A[i], sm[i - 1])
		res = []
		for i in range(1, n - 1):
			if A[i] > sm[i - 1] and A[i] < lr[i + 1]:
				res.extend([sm[i - 1], A[i], lr[i + 1]])
				break
		return res


class Solution:

	def find3number(self, A, n):
		max = n - 1
		min = 0
		smallest = [0] * n
		smallest[0] = -1
		for i in range(1, n):
			if A[i] <= A[min]:
				min = i
				smallest[i] = -1
			else:
				smallest[i] = min
		greatest = [0] * n
		greatest[n - 1] = -1
		for j in range(n - 2, -1, -1):
			if A[j] >= A[max]:
				max = j
				greatest[j] = -1
			else:
				greatest[j] = max
		resultantArray = []
		for k in range(n):
			if smallest[k] != -1 and greatest[k] != -1:
				resultantArray.append(A[smallest[k]])
				resultantArray.append(A[k])
				resultantArray.append(A[greatest[k]])
				return resultantArray
		return []


from collections import deque

class Solution:

	def find3number(self, A, n):
		smaller_than = [-1]
		greater_than = deque([-1])
		min = 0
		for i in range(1, n):
			if A[i] <= A[min]:
				smaller_than.append(-1)
				min = i
			else:
				smaller_than.append(min)
		max = n - 1
		for i in range(n - 2, -1, -1):
			if A[i] >= A[max]:
				greater_than.appendleft(-1)
				max = i
			else:
				greater_than.appendleft(max)
		greater_than = list(greater_than)
		for i in range(n):
			if greater_than[i] != -1 and smaller_than[i] != -1:
				return [A[smaller_than[i]], A[i], A[greater_than[i]]]
		return []


class Solution:

	def find3number(self, A, n):
		arr = [-1] * n
		stack = []
		for i in range(n - 1, -1, -1):
			while len(stack) > 0 and A[stack[-1]] <= A[i]:
				del stack[-1]
			if len(stack) > 0:
				arr[i] = stack[-1]
			stack.append(i)
		for i in range(n):
			if arr[i] != -1 and arr[arr[i]] != -1:
				return [A[i], A[arr[i]], A[arr[arr[i]]]]
		return []


class Solution:

	def find3number(self, A, n):
		if n < 3:
			return []
		min = A[0]
		real_min = A[0]
		number_2 = -1
		seq = 1
		for i in range(1, n):
			if A[i] < min:
				min = A[i]
			elif A[i] == min:
				continue
			elif A[i] < number_2:
				number_2 = A[i]
				real_min = min
			elif A[i] > number_2:
				if seq == 1:
					real_min = min
				seq += 1
				if seq == 3:
					return [real_min, number_2, A[i]]
				number_2 = A[i]
		return []


class Solution:

	def find3number(self, A, n):
		vec = list()
		if n < 3:
			return vec
		smaller = list()
		min = 0
		max = n - 1
		smaller = [0] * 10000
		smaller[0] = -1
		for i in range(1, n):
			if A[i] <= A[min]:
				min = i
				smaller[i] = -1
			else:
				smaller[i] = min
		greater = [0] * 10000
		greater[n - 1] = -1
		for i in range(n - 2, -1, -1):
			if A[i] > A[max]:
				max = i
				greater[i] = -1
			else:
				greater[i] = max
		for i in range(0, n):
			if smaller[i] != -1 and greater[i] != -1:
				vec.append(A[smaller[i]])
				vec.append(A[i])
				vec.append(A[greater[i]])
				return vec
		return vec


class Solution:

	def find3number(self, A, n):
		smaller = [0] * n
		bigger = [0] * n
		smaller[0] = A[0]
		bigger[n - 1] = A[n - 1]
		for i in range(1, n):
			smaller[i] = min(smaller[i - 1], A[i])
		for i in range(n - 2, -1, -1):
			bigger[i] = max(bigger[i + 1], A[i])
		for i in range(n):
			if smaller[i] < A[i] and A[i] < bigger[i]:
				return [smaller[i], A[i], bigger[i]]
		return []


from collections import OrderedDict
from sys import *

class Solution:

	def find3number(self, A, n):
		minArray = []
		maxArray = [0 for i in range(n)]
		mini = sys.maxsize
		maxi = -sys.maxsize
		for i in A:
			mini = mini if mini < i else i
			minArray.append(mini)
		for i in range(n - 1, -1, -1):
			maxi = maxi if maxi > A[i] else A[i]
			maxArray[i] = maxi
		for i in range(1, n - 1):
			if minArray[i - 1] < A[i] and A[i] < maxArray[i + 1]:
				return [minArray[i - 1], A[i], maxArray[i + 1]]
		return []