Given a preorder traversal of a BST, find the leaf nodes of the tree without building the tree.
Example 1:
Input:
N = 2
arr = {2,1}
Output: {1}
Explaination: 1 is the only leaf node.
Example 2:
Input:
N = 3
Arr = {3, 2, 4}
Output: {2, 4}
Explaination: 2, 4 are the leaf nodes.
Your Task:
You don't need to read input or print anything. Your task is to complete the function leafNodes() which takes the array arr[] and its size N as input parameters and returns the leaf nodes of the tree.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{3}
1 ≤ arr[i] ≤ 10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Range queries

Complete search

Starter code: #User function Template for python3

class Solution:

	def leafNodes(self, arr, N):

		# code here



Solutions:
class Solution:

	def leafNodes1(self, arr, N):
		global ans
		if N == 0:
			return
		if N == 1:
			ans.append(arr[0])
			return
		root = arr[0]
		index = 1
		for i in range(1, N):
			if arr[0] < arr[i]:
				index = i
				break
		self.leafNodes1(arr[1:index], len(arr[1:index]))
		self.leafNodes1(arr[index:], len(arr[index:]))

	def leafNodes(self, arr, N):
		global ans
		ans = []
		self.leafNodes1(arr, N)
		return ans


class Solution:

	def leafNodes(self, arr, N):
		(n, stack, leaf_nodes) = (N, [arr[0]], [])
		for i in range(1, n):
			if arr[i] < stack[-1]:
				stack.append(arr[i])
			else:
				(temp, removed_counter) = (stack[-1], 0)
				while stack and stack[-1] < arr[i]:
					stack.pop()
					removed_counter += 1
				stack.append(arr[i])
				if removed_counter >= 2:
					leaf_nodes.append(temp)
		leaf_nodes.append(stack[-1])
		return leaf_nodes


class Solution:

	def leafNodes(self, arr, N):
		st = []
		i = 0
		res = []
		for j in range(1, N):
			found = False
			if arr[i] > arr[j]:
				st.append(arr[i])
			else:
				while st and arr[j] > st[-1]:
					found = True
					st.pop()
			if found:
				res.append(arr[i])
			i += 1
		res.append(arr[-1])
		return res


class Solution:

	def leafNodes(self, arr, N):
		s = []
		i = 0
		ans = []
		for j in range(1, N):
			found = False
			if arr[i] > arr[j]:
				s.append(arr[i])
			else:
				while len(s) != 0:
					if arr[j] > s[-1]:
						s.pop(-1)
						found = True
					else:
						break
			if found:
				ans.append(arr[i])
			i += 1
		ans.append(arr[N - 1])
		return ans


class Solution:

	def leafNodes(self, arr, N):
		ans = []

		def solve(a):
			if 0 <= len(a) < 2:
				ans.extend(a)
				return
			root = a[0]
			i = 1
			while i < len(a) and root > a[i]:
				i += 1
			solve(a[1:i])
			solve(a[i:])
		solve(arr)
		return ans


class Solution:

	def leafNodes(self, arr, N):
		ans = []
		stack = []
		(i, j) = (0, 1)
		while j < N:
			notfound = False
			if arr[i] > arr[j]:
				stack.append(arr[i])
			else:
				while stack:
					if arr[j] > stack[-1]:
						stack.pop()
						notfound = True
					else:
						break
			if notfound:
				ans.append(arr[i])
			i += 1
			j += 1
		ans.append(arr[N - 1])
		return ans


class Solution:

	def leafNodes(self, arr, N):
		(stack, ans) = ([arr[0]], [])
		for i in range(1, len(arr)):
			if arr[i] > stack[-1]:
				(pop_count, top_elem) = (0, stack[-1])
				while stack and stack[-1] < arr[i]:
					stack.pop()
					pop_count += 1
				if pop_count >= 2:
					ans.append(top_elem)
			stack.append(arr[i])
		ans.append(stack[-1])
		return ans


class Solution:

	def leafNodes(self, arr, N):
		_stack = []
		i = 0
		_leafs = []
		for j in range(1, len(arr)):
			_found = False
			if int(arr[i]) > int(arr[j]):
				_stack.append(arr[i])
			else:
				while len(_stack) != 0:
					if int(arr[j]) > int(_stack[-1]):
						_stack.pop()
						_found = True
					else:
						break
			if _found:
				_leafs.append(arr[i])
			i += 1
		_leafs.append(arr[N - 1])
		return _leafs


import math

class Solution:

	def leafNodes(self, arr, n):
		i = 0
		leaves = []

		def dfs(min_l, max_l):
			nonlocal i, leaves, arr, n
			if i >= n:
				return False
			ele = arr[i]
			if min_l <= ele <= max_l:
				i += 1
				left = dfs(min_l, ele - 1)
				right = dfs(ele + 1, max_l)
				if not left and (not right):
					leaves.append(ele)
				return True
			else:
				return False
		dfs(-math.inf, math.inf)
		return leaves


class Solution:

	def leafNodes(self, arr, N):
		ans = []

		def dfs(index, mmin, mmax):
			nonlocal ans
			if index[0] == N - 1:
				ans.append(arr[index[0]])
				return
			node = arr[index[0]]
			lindex = index[0] + 1
			(left, right) = (None, None)
			if lindex < N and mmin < arr[lindex] <= node:
				index[0] += 1
				dfs(index, mmin, node)
				left = True
			else:
				left = None
			rindex = index[0] + 1
			if rindex < N and node <= arr[rindex] < mmax:
				index[0] += 1
				dfs(index, node, mmax)
				right = True
			else:
				right = None
			if left is None and right is None:
				ans.append(node)
		dfs([0], -float('inf'), float('inf'))
		return ans


class Solution:

	def leafNodes(self, arr, N):
		st = []
		ans = []
		for i in arr:
			if st and st[-1] < i:
				prev = st.pop()
				if st and st[-1] < i:
					ans.append(prev)
					while st and st[-1] < i:
						st.pop()
			st.append(i)
		ans.append(st[-1])
		return ans


from collections import deque

class Solution:

	def leafNodes(self, A, N):
		ans = []
		A = deque(A)

		def _solve(L, R):
			v = A.popleft()
			Lcnt = Rcnt = 0
			if A and L <= A[0] < v:
				Lcnt = _solve(L, v)
			if A and v < A[0] <= R:
				Rcnt = _solve(v, R)
			if Lcnt == 0 and Rcnt == 0:
				ans.append(v)
			return 1 + Lcnt + Rcnt
		_solve(0, 10 ** 9)
		return ans


class Solution:

	def leafNodes(self, arr, N):
		if len(arr) == 0:
			return []
		if len(arr) == 1:
			return [arr[0]]
		for i in range(1, len(arr)):
			if arr[i] > arr[0]:
				idx = i
				break
		else:
			idx = i + 1
		left = self.leafNodes(arr[1:idx], len(arr[1:idx]))
		right = self.leafNodes(arr[idx:], len(arr[idx:]))
		return left + right


from collections import deque

class Solution:

	def leafNodes(self, arr, N):
		ans = []
		stack = deque()
		stack.append(arr[0])
		if N == 1:
			return arr
		if N == 2:
			ans.append(arr[1])
			return ans
		for i in range(1, N):
			if arr[i] < stack[-1]:
				stack.append(arr[i])
			else:
				count = 0
				top = stack[-1]
				while len(stack) > 0 and arr[i] > stack[-1]:
					stack.pop()
					count += 1
				stack.append(arr[i])
				if count >= 2:
					ans.append(top)
		ans.append(stack[-1])
		return ans


class Solution:

	def leafNodes(self, arr, N):
		ans = list()
		self.solve(arr, ans)
		return ans

	def solve(self, arr, ans):
		if len(arr) < 1:
			return
		if len(arr) == 1:
			ans.append(arr[0])
			return
		root = arr[0]
		i = 1
		while len(arr) > i:
			if arr[i] <= root:
				i += 1
			else:
				break
		self.solve(arr[1:i], ans)
		self.solve(arr[i:], ans)
		return


class Solution:

	def leafNodes(self, arr, N):
		(ans, stack) = ([], [])
		stack.append(arr[0])
		for i in range(1, N):
			if arr[i] < stack[-1]:
				stack.append(arr[i])
			else:
				temp = stack[-1]
				rem = 0
				while stack != [] and stack[-1] < arr[i]:
					stack.pop()
					rem += 1
				if rem > 1:
					ans.append(temp)
				stack.append(arr[i])
		ans.append(stack.pop())
		return ans


class Solution:

	def leafNodes(self, arr, N):
		if N == 1:
			return [arr[0]]
		if N == 2:
			return [arr[-1]]
		stack = [arr[0]]
		res = []
		for i in range(1, N):
			if arr[i] < stack[-1]:
				stack.append(arr[i])
			else:
				check = stack.pop()
				if len(stack) > 0 and arr[i] >= stack[-1]:
					res.append(check)
				while len(stack) > 0 and arr[i] >= stack[-1]:
					stack.pop()
				stack.append(arr[i])
		res.append(stack[-1])
		return res


class Solution:

	def leafNodes(self, arr, N):
		ans = []
		s = []
		s.append(arr[0])
		for i in range(1, N):
			if arr[i] < s[-1]:
				s.append(arr[i])
			else:
				remove = 0
				temp = s[-1]
				while s and s[-1] < arr[i]:
					s.pop()
					remove += 1
				s.append(arr[i])
				if remove >= 2:
					ans.append(temp)
		ans.append(s[-1])
		return ans


class Solution:

	def leafNodes(self, arr, N):
		sol = []
		stk = []
		i = 0
		for j in range(1, N):
			flag = False
			if arr[i] > arr[j]:
				stk.append(arr[i])
			else:
				while len(stk) > 0:
					if arr[j] > stk[-1]:
						stk.pop()
						if not flag:
							sol.append(arr[i])
						flag = True
					else:
						break
			i += 1
		sol.append(arr[-1])
		return list(sol)


class Solution:

	def leafNodes(self, arr, n):
		st = []
		ans = []
		st.append(arr[0])
		for i in range(1, n):
			if arr[i] < st[-1]:
				st.append(arr[i])
			else:
				temp = st[-1]
				st.pop()
				if st and arr[i] > st[-1]:
					while st and arr[i] > st[-1]:
						st.pop()
					ans.append(temp)
				st.append(arr[i])
		ans.append(arr[n - 1])
		return ans


class Solution:

	def leafNodes(self, arr, N):
		ans = []
		stack = []
		stack.append(arr[0])
		i = 1
		while i < len(arr):
			if arr[i] < stack[-1]:
				stack.append(arr[i])
			else:
				top = stack[-1]
				stack.pop()
				if stack and arr[i] > stack[-1]:
					while stack and arr[i] > stack[-1]:
						stack.pop()
					ans.append(top)
				stack.append(arr[i])
			i += 1
		ans.append(arr[-1])
		return ans


class Solution:

	def leafNodes(self, arr, N):
		ret = []

		def collect(xs):
			nonlocal ret
			if len(xs) <= 1:
				if xs:
					ret.append(xs[0])
				return
			collect([x for x in xs if x < xs[0]])
			collect([x for x in xs if x > xs[0]])
		collect(arr)
		return ret


class Solution:

	def leafNodes(self, arr, n):
		ans = []
		stack = [arr[0]]
		for i in range(1, n):
			if arr[i] < stack[-1]:
				stack.append(arr[i])
			else:
				leaf = stack[-1]
				stack.pop()
				if stack and arr[i] > stack[-1]:
					while stack and arr[i] > stack[-1]:
						stack.pop()
					ans.append(leaf)
				stack.append(arr[i])
		ans.append(arr[-1])
		return ans


class Solution:

	def leafNodes(self, a, n):
		ans = []
		stack = []
		stack.append(a[0])
		for i in range(1, n):
			if a[i] < stack[-1]:
				stack.append(a[i])
			else:
				tmp = stack[-1]
				stack.pop(-1)
				if len(stack) != 0 and a[i] > stack[-1]:
					while len(stack) != 0 and a[i] > stack[-1]:
						stack.pop(-1)
					ans.append(tmp)
				stack.append(a[i])
		ans.append(a[n - 1])
		return ans


from collections import deque
from bisect import bisect_left

class Solution:

	def solve(self, pre, ino, ans):
		if len(ino) == 0:
			return
		if len(ino) == 1:
			pre.popleft()
			ans.append(ino[0])
			return
		else:
			node = pre.popleft()
			i = bisect_left(ino, node)
			self.solve(pre, ino[0:i], ans)
			self.solve(pre, ino[i + 1:], ans)

	def leafNodes(self, pre, N):
		pre = deque(pre)
		ino = sorted(pre)
		global ans
		ans = []
		self.solve(pre, ino, ans)
		return ans


class Solution:

	def leafNodes(self, arr, n):
		ans = []
		s = []
		j = 0
		for i in range(1, n):
			if arr[j] > arr[i]:
				s.append(arr[j])
			else:
				valid = False
				while s:
					if arr[i] > s[-1]:
						s.pop()
						valid = True
					else:
						break
				if valid:
					ans.append(arr[j])
			i += 1
			j += 1
		ans.append(arr[-1])
		return ans


class Solution:

	def leafNodes(self, arr, N):
		l1 = []
		ans = []
		for x in arr:
			if l1 and l1[-1] < x:
				prev = l1.pop()
				if l1 and l1[-1] < x:
					ans.append(prev)
					while l1 and l1[-1] < x:
						l1.pop()
			l1.append(x)
		ans.append(l1[-1])
		return ans


class Solution:

	def leafNodes(self, arr, N):
		if N < 1:
			return []
		stack = [arr[0]]
		ans = []
		for i in range(1, N):
			if arr[i] > stack[-1]:
				iniSize = len(stack)
				while len(stack) > 0 and stack[-1] < arr[i]:
					stack.pop()
				if iniSize - len(stack) > 1:
					ans.append(arr[i - 1])
			stack.append(arr[i])
		ans.append(stack[-1])
		return ans


class Solution:
	temp = []

	def leafNodes(self, arr, N):
		temp = []

		def fleaf(pre):
			n = len(pre)
			if n == 1:
				temp.append(pre[0])
				return
			if n < 1:
				return
			left = pre[0]
			for i in range(1, n):
				if pre[i] > left:
					fleaf(pre[1:i])
					fleaf(pre[i:])
					break
			else:
				fleaf(pre[1:n])
		fleaf(arr)
		return temp


class Solution:

	def leafNodes(self, arr, N):
		stk = []
		res = []
		for i in range(N):
			if len(stk) > 0 and stk[-1] < arr[i]:
				leaf = stk[-1]
				count = 0
				while len(stk) > 0 and stk[-1] < arr[i]:
					stk.pop()
					count = count + 1
				stk.append(arr[i])
				if count > 1:
					res.append(leaf)
			else:
				stk.append(arr[i])
		res.append(stk[-1])
		return res


class Solution:

	def leafNodes(self, arr, N):
		mx = []
		leaf = []
		prev = arr[0]
		flag = 0
		for i in range(1, N):
			if arr[i] < prev:
				mx.append(prev)
				prev = arr[i]
			else:
				flag = 0
				while mx:
					root = mx.pop()
					if root < arr[i]:
						flag = 1
					else:
						mx.append(root)
						break
				if flag == 1:
					leaf.append(prev)
				prev = arr[i]
		leaf.append(prev)
		return leaf


class Solution:

	def leafNodes(self, arr, N):
		st = []
		leaf = []
		st.append(arr[0])
		t = 0
		for i in range(1, N):
			if arr[i] > st[t]:
				if t > 0 and arr[i] > st[t - 1]:
					leaf.append(st.pop())
					t -= 1
				while t >= 0 and st[t] < arr[i]:
					st.pop()
					t -= 1
				st.append(arr[i])
				t += 1
			else:
				st.append(arr[i])
				t += 1
		leaf.append(arr[N - 1])
		return leaf


def leafNodeHelper(preorder, inorder, pl, pu, il, ih, ans):
	if pl == pu:
		ans.append(preorder[pl])
		return
	if pl > pu:
		return
	rIndex = il
	while True:
		if preorder[pl] == inorder[rIndex]:
			break
		rIndex += 1
	Index = rIndex - il
	leafNodeHelper(preorder, inorder, pl + 1, pl + Index, il, rIndex - 1, ans)
	leafNodeHelper(preorder, inorder, pl + Index + 1, pu, rIndex + 1, ih, ans)

class Solution:

	def leafNodes(self, arr, N):
		preorder = arr
		temp = arr.copy()
		temp.sort()
		inorder = temp
		ans = []
		leafNodeHelper(preorder, inorder, 0, N - 1, 0, N - 1, ans)
		return ans


from bisect import bisect_left

class Solution:

	def leafNodesUtil(self, arr, lo, hi, out):
		if lo < hi:
			root = arr[lo]
			rootind = lo
			ind = bisect_left(arr, root, lo=rootind + 1, hi=hi)
			if ind <= rootind + 1 and ind >= hi:
				out.append(root)
			else:
				self.leafNodesUtil(arr, rootind + 1, ind, out)
				self.leafNodesUtil(arr, ind, hi, out)

	def leafNodes(self, arr, N):
		out = []
		self.leafNodesUtil(arr, 0, N, out)
		return out


class Solution:

	def leafNodes(self, arr, N):
		ind = -1
		res = []

		def recur(low, high):
			nonlocal res, ind
			ind += 1
			if ind >= N or arr[ind] < low or arr[ind] > high:
				ind -= 1
				return -1
			else:
				val = arr[ind]
				v1 = recur(low, val)
				v2 = recur(val, high)
				if v1 == -1 and v2 == -1:
					res.append(val)
				return 0
		recur(-float('inf'), float('inf'))
		return res


class Solution:

	def leafNodes(self, A, N):
		ans = []
		stack = []
		for x in A:
			if stack and stack[-1] < x:
				prev = stack.pop()
				if stack and stack[-1] < x:
					ans.append(prev)
					while stack and stack[-1] < x:
						stack.pop()
			stack.append(x)
		ans.append(stack[-1])
		return ans


st = ''
out = []

def check(arr):
	global st
	global out
	if len(arr) == 0:
		return
	if len(arr) == 1:
		st = st[1:]
		out.append(arr[0])
		return
	else:
		j = arr.index(st[0])
		st = st[1:]
		check(arr[0:j])
		check(arr[j + 1:])
		return

class Solution:

	def leafNodes(self, arr, N):
		global st
		global out
		out = []
		st = arr
		b = sorted(arr)
		check(b)
		return out


class Solution:

	def leafNodes(self, A, N):
		ans = []
		stk = []
		j = 0
		for i in range(1, N):
			if A[j] > A[i]:
				stk.append(A[j])
			else:
				f = False
				while stk:
					if A[i] > stk[-1]:
						stk.pop()
						f = True
					else:
						break
				if f:
					ans.append(A[j])
			j += 1
		ans.append(A[-1])
		return ans


class Solution:

	def leafNodes(self, arr, N):
		stack = []
		output = []
		for num in arr:
			possibleLeafNode = None
			totalRemoved = 0
			while stack and stack[-1] < num:
				if not possibleLeafNode:
					possibleLeafNode = stack[-1]
				stack.pop()
				totalRemoved += 1
			if totalRemoved >= 2:
				output.append(possibleLeafNode)
			stack.append(num)
		output.append(arr[-1])
		return output


class Solution:

	def leafNodes(self, arr, N):
		ans = []
		stack = []
		for i in range(N):
			if len(stack) == 0:
				stack.append(arr[i])
			elif arr[i] < stack[-1]:
				stack.append(arr[i])
			else:
				temp = stack[-1]
				n = 0
				while len(stack) != 0 and arr[i] > stack[-1]:
					stack.pop()
					n += 1
				stack.append(arr[i])
				if n >= 2:
					ans.append(temp)
		ans.append(stack[-1])
		return ans


class Solution:

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


class Solution:

	def leafNodes(self, arr, N):
		st = []
		lis = []
		st.append(arr[0])
		for i in range(1, N):
			if arr[i] < st[-1]:
				st.append(arr[i])
			else:
				temp = st[-1]
				count = 0
				while len(st) != 0 and st[-1] < arr[i]:
					st.pop()
					count += 1
				st.append(arr[i])
				if count >= 2:
					lis.append(temp)
		lis.append(st[-1])
		return lis


class Solution:

	def leafNodes(self, arr, N):
		stack = []
		res = []
		for i in range(N - 1):
			if arr[i] > arr[i + 1]:
				stack.append(arr[i])
			elif stack and arr[i + 1] > stack[-1]:
				res.append(arr[i])
				while stack and stack[-1] < arr[i + 1]:
					stack.pop()
		res.append(arr[N - 1])
		return res


class Solution:

	def leafNodes(self, arr, N):
		st = []
		l = []
		for i in range(N - 1):
			f = 0
			if arr[i] > arr[i + 1]:
				st.append(arr[i])
			else:
				while len(st) > 0:
					if arr[i + 1] > st[-1]:
						st.pop(-1)
						f = 1
					else:
						break
			if f == 1:
				l.append(arr[i])
		l.append(arr[-1])
		return l


class Solution:

	def leafNodes(self, arr, N):
		if len(arr) == 1:
			return arr
		stack = []
		leafNode = []
		stack.append(arr[0])
		i = 1
		while i < len(arr):
			if arr[i] <= stack[-1]:
				stack.append(arr[i])
			else:
				temp = stack[-1]
				removed = 0
				while stack and arr[i] > stack[-1]:
					stack.pop()
					removed += 1
				stack.append(arr[i])
				if removed >= 2:
					leafNode.append(temp)
			i += 1
		leafNode.append(stack[-1])
		return leafNode


class Solution:

	def leafNodes(self, arr, N):
		ans = []
		st = [arr[0]]
		for i in range(1, N):
			if arr[i] < st[-1]:
				st.append(arr[i])
			else:
				top = st[-1]
				co = 0
				while st and st[-1] < arr[i]:
					co += 1
					st.pop()
				st.append(arr[i])
				if co > 1:
					ans.append(top)
		ans.append(st.pop())
		return sorted(ans)


class Solution:

	def leafNodes(self, arr, N):
		(i, j) = (0, 1)
		stack = []
		result = []
		while j < N:
			if arr[i] > arr[j]:
				stack.append(arr[i])
			else:
				flag = False
				while stack and stack[-1] < arr[j]:
					flag = True
					stack.pop()
				if flag:
					result.append(arr[i])
			i += 1
			j += 1
		result.append(arr[i])
		return result


class Solution:

	def leafNodes(self, arr, N):
		ans = []
		s = []
		(i, j) = (0, 1)
		while j < N:
			flag = False
			if arr[i] > arr[j]:
				s.append(arr[i])
			else:
				while s and s[-1] < arr[j]:
					s.pop()
					flag = True
			if flag:
				ans.append(arr[i])
			i += 1
			j += 1
		ans.append(arr[N - 1])
		return ans


class Solution:

	def leafNodes(self, arr, N):
		ans = []
		stack = [arr[0]]
		for i in range(1, N):
			if arr[i] < stack[-1]:
				stack.append(arr[i])
			else:
				a = stack.pop()
				b = 0
				while len(stack) > 0 and stack[-1] < arr[i]:
					stack.pop()
					b = 1
				if b == 1:
					ans.append(a)
				stack.append(arr[i])
		ans.append(arr[-1])
		return ans


class Tree:

	def __init__(self, val=0, left=None, right=None):
		self.val = val
		self.left = left
		self.right = right

class Solution:

	def leafNodes(self, arr, N):
		stack = []
		ans = []
		for x in arr:
			if stack and stack[-1] < x:
				prev = stack.pop()
				if stack and stack[-1] < x:
					ans.append(prev)
					while stack and stack[-1] < x:
						stack.pop()
			stack.append(x)
		ans.append(stack[-1])
		return ans


class Solution:

	def leafNodes(self, A, N):
		(st, res) = ([], [])
		st.append(A[0])
		for i in range(1, N):
			(j, t) = (0, st[-1])
			while st and st[-1] < A[i]:
				st.pop()
				j += 1
			if j > 1:
				res.append(t)
			st.append(A[i])
		res.append(st[-1])
		return res


import bisect

class Solution:

	def leafNodes(self, arr, N):
		res = []

		def make(arr):
			if len(arr) == 1:
				res.append(arr[0])
			if not arr:
				return
			x = arr[0]
			del arr[0]
			y = bisect.bisect_left(arr, x)
			make(arr[:y])
			make(arr[y:])
		make(arr)
		return res


class Solution:

	def leafNodes(self, arr, N):
		A = []

		def sol(a):
			if 0 <= len(a) < 2:
				A.extend(a)
				return
			ro = a[0]
			i = 1
			while i < len(a) and ro > a[i]:
				i += 1
			sol(a[1:i])
			sol(a[i:])
		sol(arr)
		return A


class Solution:

	def leafNodesHelper(self, l, r, arr, leaves):
		if l > r:
			return
		if l == r:
			leaves.append(arr[l])
			return
		mid = l + 1
		while mid <= r and arr[mid] < arr[l]:
			mid += 1
		self.leafNodesHelper(l + 1, mid - 1, arr, leaves)
		self.leafNodesHelper(mid, r, arr, leaves)

	def leafNodes(self, arr, N):
		leaves = []
		self.leafNodesHelper(0, N - 1, arr, leaves)
		return leaves


class Solution:

	def leafNodes(self, arr, n):
		ans = list()
		j = 0
		s = list()
		for i in range(1, n):
			f = 1
			if arr[j] > arr[i]:
				s.append(arr[j])
			else:
				while len(s) != 0:
					if arr[i] > s[-1]:
						s.pop(-1)
						f = 0
					else:
						break
			if f == 0:
				ans.append(arr[j])
			j += 1
		ans.append(arr[n - 1])
		return ans
		ans.append(preorder[n - 1])
		return ans