Given array A[] of integers, the task is to complete the function findMaxDiff which finds the maximum absolute difference between nearest left and right smaller element of every element in array.If the element is the leftmost element, nearest smaller element on left side is considered as 0. Similarly if the element is the rightmost elements, smaller element on right side is considered as 0.
Examples:
Input : arr[] = {2, 1, 8}
Output : 1
Left smaller  LS[] {0, 0, 1}
Right smaller RS[] {1, 0, 0}
Maximum Diff of abs(LS[i] - RS[i]) = 1 
Input  : arr[] = {2, 4, 8, 7, 7, 9, 3}
Output : 4
Left smaller   LS[] = {0, 2, 4, 4, 4, 7, 2}
Right smaller  RS[] = {0, 3, 7, 3, 3, 3, 0}
Maximum Diff of abs(LS[i] - RS[i]) = 7 - 3 = 4 
Input : arr[] = {5, 1, 9, 2, 5, 1, 7}
Output : 1
Input:
The first line of input contains an integer T denoting the no of test cases. Then T test cases follow .Each test case contains an integer N denoting the size of the array A. In the next line are N space separated values of the array A.
Output:
For each test case output will be in a new line denoting the the maximum absolute difference between nearest left and right smaller element of every element in array.
Constraints:
1<=T<=100
1<=N<=100
1<=A[ ]<=100
Example(To be used only for expected output) :
Input:
2
3
2 1 8
7
2 4 8 7 7 9 3
Output
1
4

Difficulty: MEDIUM
Tags: Data structures
Skill types: Data structures

Starter code:
class Solution:

    # Your task is to complete this function

    # Function should return an integer denoting the required answer

    def findMaxDiff(self, arr, n):

        # Code here

Solutions:
class Solution:

	def findMaxDiff(self, arr, n):
		Ans = [0] * n
		stack = []
		for i in range(n):
			rightvalue = 0
			if i + 1 < n:
				for value in arr[i + 1:]:
					if value < arr[i]:
						rightvalue = value
						break
			leftvalue = 0
			while stack:
				value = stack[-1]
				if value < arr[i]:
					leftvalue = value
					break
				else:
					stack.pop()
			stack.append(arr[i])
			Ans[i] = abs(rightvalue - leftvalue)
		return max(Ans)


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

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

class Solution:

	def findMaxDiff(self, a, n):
		nrs = nearestrightsmaller(a, n)
		nls = nearestleftsmaller(a, n)
		res = 0
		for i in range(n):
			res = max(res, abs(nls[i] - nrs[i]))
		return res


class Solution:

	def findMaxDiff(self, arr, n):
		left = [0]
		for i in range(1, len(arr)):
			k = arr[:i][::-1]
			for j in k:
				if j < arr[i]:
					left.append(j)
					break
			else:
				left.append(0)
		right = []
		for i in range(len(arr)):
			k = arr[i + 1:]
			for j in k:
				if j < arr[i]:
					right.append(j)
					break
			else:
				right.append(0)
		diff = abs(left[0] - right[0])
		for i in range(1, len(arr)):
			d = abs(left[i] - right[i])
			if d > diff:
				diff = d
		return diff


class Solution:

	def findMaxDiff(self, arr, n):
		stack = []
		ans_left = [0] * n
		ans_right = [0] * n
		for i in range(n):
			while len(stack) > 0 and stack[-1] >= arr[i]:
				stack.pop()
			if stack:
				ans_left[i] = stack[-1]
			else:
				ans_left[i] = 0
			stack.append(arr[i])
		stack.clear()
		for i in range(n - 1, -1, -1):
			while len(stack) > 0 and stack[-1] >= arr[i]:
				stack.pop()
			if stack:
				ans_right[i] = stack[-1]
			else:
				ans_right[i] = 0
			stack.append(arr[i])
		ans = 0
		for i in range(n):
			ans = max(abs(ans_left[i] - ans_right[i]), ans)
		return ans


from typing import List
from collections import deque

class Solution:

	def findMaxDiff(self, a: List[int], n: int) -> int:
		str = deque()
		ls = [0] * n
		rs = [0] * n
		for i in range(n):
			while str and str[-1] >= a[i]:
				str.pop()
			if not str:
				ls[i] = 0
			else:
				ls[i] = str[-1]
			str.append(a[i])
		str.clear()
		for i in range(n - 1, -1, -1):
			while str and str[-1] >= a[i]:
				str.pop()
			if not str:
				rs[i] = 0
			elif str[-1] < a[i]:
				rs[i] = str[-1]
			str.append(a[i])
		ans = 0
		for i in range(n):
			ans = max(ans, abs(ls[i] - rs[i]))
		return ans


def nearestleft(arr, n):
	stack = []
	ans = []
	for i in range(n):
		while len(stack) != 0:
			if arr[i] > stack[-1]:
				ans.append(stack[-1])
				break
			else:
				stack.pop()
		if len(stack) == 0:
			ans.append(0)
		stack.append(arr[i])
	return ans

def nearestright(arr, n):
	stack = []
	ans = []
	for i in range(n - 1, -1, -1):
		while len(stack) != 0:
			if arr[i] > stack[-1]:
				ans.append(stack[-1])
				break
			else:
				stack.pop()
		if len(stack) == 0:
			ans.append(0)
		stack.append(arr[i])
	return ans

class Solution:

	def findMaxDiff(self, arr, n):
		left = nearestleft(arr, n)
		right = nearestright(arr, n)
		diff = 0
		for i in range(n):
			if abs(left[i] - right[n - i - 1]) > diff:
				diff = abs(left[i] - right[n - i - 1])
		return diff


class Solution:

	def findMaxDiff(self, arr, n):
		NSL = []
		NSR = []
		max_diff = []
		for i in range(len(arr)):
			for j in range(i - 1, -1, -1):
				if i == 0:
					NSL.append(0)
					break
				if arr[i] > arr[j]:
					NSL.append(arr[j])
					break
			else:
				NSL.append(0)
			for k in range(i + 1, n):
				if i == n - 1:
					NSR.append(0)
					break
				if arr[i] > arr[k]:
					NSR.append(arr[k])
					break
			else:
				NSR.append(0)
			max_diff.append(abs(NSL[i] - NSR[i]))
		result = max(max_diff)
		return result


class Solution:

	def findMaxDiff(self, arr, n):
		ls = [0]
		rs = []
		n = len(arr)
		for i in range(1, n):
			d = len(ls)
			for j in range(i - 1, -1, -1):
				if arr[j] < arr[i]:
					ls.append(arr[j])
					break
			if len(ls) == d:
				ls.append(0)
			else:
				continue
		for i in range(n):
			c = len(rs)
			for j in range(i + 1, n):
				if arr[i] > arr[j]:
					rs.append(arr[j])
					break
			if len(rs) == c:
				rs.append(0)
			else:
				continue
		maxx = 0
		for (i, j) in zip(ls, rs):
			maxx = max(maxx, abs(i - j))
		return maxx


class Solution:

	def findMaxDiff(self, arr, n):
		st = [-1]
		arr.append(0)
		ans = 0
		for i in range(len(arr)):
			while arr[st[-1]] > arr[i]:
				cur = arr[st.pop()]
				cur_ans = abs(arr[i] - arr[st[-1]])
				ans = max(ans, cur_ans)
			if len(st) > 1 and arr[st[-1]] == arr[i]:
				continue
			st.append(i)
		return ans


class Solution:

	def findMaxDiff(self, arr, n):
		maxdiff = 0
		left = smallestLeft(arr, n)
		right = smallestRight(arr, n)
		for i in range(n):
			maxdiff = max(maxdiff, abs(left[i] - right[i]))
		return maxdiff

def smallestLeft(a, n):
	stack = []
	result = []
	for i in range(n):
		while stack and stack[-1] >= a[i]:
			stack.pop()
		if stack:
			result.append(stack[-1])
		else:
			result.append(0)
		stack.append(a[i])
	return result

def smallestRight(a, n):
	stack = []
	result = []
	for i in range(n - 1, -1, -1):
		while stack and stack[-1] >= a[i]:
			stack.pop()
		if stack:
			result.append(stack[-1])
		else:
			result.append(0)
		stack.append(a[i])
	return result[::-1]


class Solution:

	def findMaxDiff(self, arr, n):
		L = [0] * n
		R = [0] * n
		for i in range(1, n):
			for j in range(i - 1, -1, -1):
				if arr[i] > arr[j]:
					L[i] = arr[j]
					break
			for k in range(i, n):
				if arr[i - 1] > arr[k]:
					R[i - 1] = arr[k]
					break
		s = []
		for i in range(0, n):
			s.append(abs(L[i] - R[i]))
		return max(s)


class Solution:

	def findMaxDiff(self, arr, n):
		i = 0
		l = arr
		(lr, ll) = ([], [])
		while i < n:
			j = i + 1
			while j < n:
				if l[j] < l[i]:
					lr.append(l[j])
					break
				j += 1
				if j == n:
					lr.append(0)
			i += 1
			if i == n:
				lr.append(0)
				break
		i = n - 1
		while i >= 0:
			j = i - 1
			while j >= 0:
				if l[j] < l[i]:
					ll.append(l[j])
					break
				j -= 1
				if j == -1:
					ll.append(0)
			i -= 1
			if i <= 0:
				ll.append(0)
				break
		return max([abs(ll[::-1][i] - lr[i]) for i in range(len(ll))])


class Solution:

	def findMaxDiff(self, arr, n):
		ls = []
		rs = []
		for i in range(n):
			try:
				x = arr[:i]
				x = x[::-1]
				f = 0
				for j in x:
					if j < arr[i]:
						ls.append(j)
						f = 1
						break
				if f == 0:
					ls.append(0)
			except:
				ls.append(0)
		for i in range(n - 1, -1, -1):
			try:
				x = arr[i:]
				f = 0
				for j in x:
					if j < arr[i]:
						rs.append(j)
						f = 1
						break
				if f == 0:
					rs.append(0)
			except:
				rs.append(0)
		rs = rs[::-1]
		answer = -1
		for i in range(len(rs)):
			if abs(ls[i] - rs[i]) > answer:
				answer = abs(ls[i] - rs[i])
		return answer


class Solution:

	def findMaxDiff(self, arr, n):
		left_smaller = []
		x = []
		for i in arr:
			while x and i <= x[-1]:
				x.pop()
			if not x:
				left_smaller.append(0)
			else:
				left_smaller.append(x[-1])
			x.append(i)
		right_smaller = []
		z = []
		for i in arr[::-1]:
			while z and i <= z[-1]:
				z.pop()
			if not z:
				right_smaller.append(0)
			else:
				right_smaller.append(z[-1])
			z.append(i)
		right_smaller = right_smaller[::-1]
		ans = abs(left_smaller[0] - right_smaller[0])
		for i in range(1, len(left_smaller)):
			ans = max(ans, abs(left_smaller[i] - right_smaller[i]))
		return ans


class Solution:

	def findMaxDiff(self, arr, n):

		def _gen_mono_stack(reverse):
			stk = [0]
			gen = reversed(arr) if reverse else arr
			for v in gen:
				while v <= stk[-1]:
					stk.pop()
				yield stk[-1]
				stk.append(v)
		Ls = _gen_mono_stack(False)
		Rs = reversed(list(_gen_mono_stack(True)))
		return max((abs(a - b) for (a, b) in zip(Ls, Rs)))


class Solution:

	def findMaxDiff(self, arr, n):

		def _gen_mono_stack(gen):
			(ans, stk) = ([], [0])
			for v in gen:
				while v <= stk[-1]:
					stk.pop()
				ans.append(stk[-1])
				stk.append(v)
			return ans
		Ls = _gen_mono_stack(arr)
		Rs = reversed(_gen_mono_stack(reversed(arr)))
		return max((abs(a - b) for (a, b) in zip(Ls, Rs)))


class Solution:

	def findMaxDiff(self, arr, n):
		lss = [0]
		rss = [0]
		for i in range(1, n):
			if arr[i] > arr[i - 1]:
				lss.append(arr[i - 1])
			else:
				m = 0
				for k in range(len(lss) - 1, -1, -1):
					if lss[k] < arr[i]:
						m = lss[k]
						break
				lss.append(m)
		for j in range(n - 2, -1, -1):
			if arr[j] > arr[j + 1]:
				rss.append(arr[j + 1])
			else:
				m = 0
				for k in range(len(rss) - 1, -1, -1):
					if rss[k] < arr[j]:
						m = rss[k]
						break
				rss.append(m)
		rsss = rss[::-1]
		res = 0
		for i in range(n):
			res = max(res, abs(lss[i] - rsss[i]))
		return res


class Solution:

	def findMaxDiff(self, arr, n):
		stack = []
		ls = [0] * n
		for i in range(n):
			while stack != [] and stack[-1] >= arr[i]:
				stack.pop()
			if stack == []:
				ls[i] = 0
			else:
				ls[i] = stack[-1]
			stack.append(arr[i])
		stack = []
		rs = [0] * n
		for i in range(n - 1, -1, -1):
			while stack != [] and stack[-1] >= arr[i]:
				stack.pop()
			if stack == []:
				rs[i] = 0
			else:
				rs[i] = stack[-1]
			stack.append(arr[i])
		m = 0
		for i in range(n):
			m = max(m, abs(ls[i] - rs[i]))
		return m


class Solution:

	def findMaxDiff(self, arr, N):
		left = [0] * N
		right = [0] * N
		stack = []
		for i in range(N):
			while stack and arr[stack[-1]] >= arr[i]:
				stack.pop()
			left[i] = arr[stack[-1]] if stack else 0
			stack.append(i)
		stack = []
		for i in range(N - 1, -1, -1):
			while stack and arr[stack[-1]] >= arr[i]:
				stack.pop()
			right[i] = arr[stack[-1]] if stack else 0
			stack.append(i)
		maxdiff = 0
		for (i, j) in zip(left, right):
			diff = abs(i - j)
			maxdiff = max(maxdiff, diff)
		return maxdiff


class Solution:

	def findMaxDiff(self, arr, n):
		l = []
		ll = []
		ls = []
		for i in arr:
			while l and i <= l[-1]:
				l.pop()
			if len(l) == 0:
				ls.append(0)
			else:
				ls.append(l[-1])
			l.append(i)
		rs = []
		for i in reversed(arr):
			while ll and i <= ll[-1]:
				ll.pop()
			if len(ll) == 0:
				rs.append(0)
			else:
				rs.append(ll[-1])
			ll.append(i)
		rs.reverse()
		g = 0
		for (i, j) in zip(ls, rs):
			if abs(i - j) > g:
				g = abs(i - j)
		return g
		print(ls, rs)


class Solution:

	def findMaxDiff(self, arr, n):
		l1 = []
		for i in range(n):
			if i == 0:
				l1.append(0)
			else:
				for j in range(i - 1, -1, -1):
					if arr[j] < arr[i]:
						l1.append(arr[j])
						break
				else:
					l1.append(0)
		l2 = []
		for i in range(n - 1, -1, -1):
			if i == n - 1:
				l2.append(0)
			else:
				for j in range(i + 1, n):
					if arr[j] < arr[i]:
						l2.append(arr[j])
						break
				else:
					l2.append(0)
		res = 0
		for i in range(n):
			res = max(res, abs(l1[i] - l2[n - 1 - i]))
		return res


class Solution:

	def findMaxDiff(self, arr, n):
		st = []
		ls = []
		rs = []
		for i in range(n):
			st.append(arr[i])
			if i == 0:
				ls.append(0)
			else:
				j = len(st) - 1
				s = len(ls)
				while j >= 0:
					if st[j] < arr[i]:
						ls.append(st[j])
						break
					j -= 1
				if len(ls) == s:
					ls.append(0)
		for i in range(n):
			if i == n - 1:
				rs.append(0)
			else:
				j = i
				s = len(rs)
				while j < len(st):
					if arr[i] > st[j]:
						rs.append(st[j])
						break
					j += 1
				if len(rs) == s:
					rs.append(0)
		maxi = 0
		for i in range(n):
			maxi = max(maxi, abs(ls[i] - rs[i]))
		return maxi


class Solution:

	def findMaxDiff(self, arr, n):
		st = []
		ls = [0] * n
		rs = [0] * n
		for i in range(n):
			while len(st) != 0 and arr[st[-1]] >= arr[i]:
				st.pop()
			if len(st) == 0:
				ls[i] = 0
			else:
				ls[i] = arr[st[-1]]
			st.append(i)
		st = []
		for i in range(n - 1, -1, -1):
			while len(st) != 0 and arr[st[-1]] >= arr[i]:
				st.pop()
			if len(st) == 0:
				rs[i] = 0
			else:
				rs[i] = arr[st[-1]]
			st.append(i)
		maxi = 0
		for i in range(n):
			maxi = max(maxi, abs(ls[i] - rs[i]))
		return maxi


class Solution:

	def findMaxDiff(self, arr, n):
		ls = [0 for a in range(n)]
		for i in range(n):
			for j in range(i - 1, -1, -1):
				if arr[i] > arr[j]:
					ls[i] = arr[j]
					break
		rs = [0 for a in range(n)]
		for i in range(n):
			for j in range(i + 1, n):
				if arr[i] > arr[j]:
					rs[i] = arr[j]
					break
		diff = 0
		for i in range(n):
			if abs(ls[i] - rs[i]) > diff:
				diff = abs(ls[i] - rs[i])
		return diff


class Solution:

	def findMaxDiff(self, arr, n):
		lsmaller = [0 for _ in range(n)]
		rsmaller = [0 for _ in range(n)]
		stack = [0]
		for i in range(1, n):
			if arr[i] > arr[stack[-1]]:
				lsmaller[i] = arr[stack[-1]]
				stack.append(i)
			else:
				while len(stack) > 0 and arr[stack[-1]] >= arr[i]:
					idx = stack.pop()
				if len(stack) == 0:
					lsmaller[i] = 0
				else:
					lsmaller[i] = arr[stack[-1]]
				stack.append(i)
		arr = arr[::-1]
		stack = [0]
		for i in range(1, n):
			if arr[i] > arr[stack[-1]]:
				rsmaller[i] = arr[stack[-1]]
				stack.append(i)
			else:
				while len(stack) > 0 and arr[stack[-1]] >= arr[i]:
					idx = stack.pop()
				if len(stack) == 0:
					rsmaller[i] = 0
				else:
					rsmaller[i] = arr[stack[-1]]
				stack.append(i)
		rsmaller = rsmaller[::-1]
		ans = 0
		for i in range(n):
			ans = max(ans, abs(lsmaller[i] - rsmaller[i]))
		return ans


class Solution:

	def findMaxDiff(self, arr, n):
		l1 = []
		l2 = []
		for i in range(n):
			j = i
			c = 0
			while j >= 0:
				if arr[i] > arr[j]:
					l1.append(arr[j])
					c = 1
					break
				j -= 1
			if c == 0:
				l1.append(0)
			k = i + 1
			c1 = 0
			while k < n:
				if arr[i] > arr[k]:
					l2.append(arr[k])
					c1 = 1
					break
				k += 1
			if c1 == 0:
				l2.append(0)
		m = 0
		for i in range(n):
			if abs(l1[i] - l2[i]) >= m:
				m = abs(l1[i] - l2[i])
		return m


class Solution:

	def findMaxDiff(self, arr, n):
		stack = []
		leftsmall = [0] * n
		for i in range(0, n):
			while stack and arr[i] <= stack[-1]:
				stack.pop()
			if len(stack) > 0:
				leftsmall[i] = stack[-1]
			else:
				leftsmall[i] = 0
			stack.append(arr[i])
		stack = []
		rightsmall = [0] * n
		maxdiff = 0
		for i in range(n - 1, -1, -1):
			while stack and arr[i] <= stack[-1]:
				stack.pop()
			if len(stack) > 0:
				rightsmall[i] = stack[-1]
			else:
				rightsmall[i] = 0
			stack.append(arr[i])
		for i in range(0, n):
			maxdiff = max(maxdiff, abs(leftsmall[i] - rightsmall[i]))
		return maxdiff


class Solution:

	def findMaxDiff(self, arr, n):
		stack1 = [0]
		stack2 = []
		stack3 = [arr[0]]
		for i in range(1, n):
			if arr[i] > stack3[-1]:
				stack1.append(stack3[-1])
				stack3.append(arr[i])
			else:
				while stack3 != []:
					if arr[i] > stack3[-1]:
						stack1.append(stack3[-1])
						break
					else:
						stack3.pop()
				if stack3 == []:
					stack1.append(0)
				stack3.append(arr[i])
		stack4 = [arr[-1]]
		stack2 = [0]
		for i in range(-2, -n - 1, -1):
			if arr[i] > stack4[-1]:
				stack2.append(stack4[-1])
				stack4.append(arr[i])
			else:
				while stack4 != []:
					if arr[i] > stack4[-1]:
						stack2.append(stack4[-1])
						break
					else:
						stack4.pop()
				if stack4 == []:
					stack2.append(0)
				stack4.append(arr[i])
		stack2 = stack2[::-1]
		maximum = 0
		for i in range(n):
			maximum = max(maximum, abs(stack2[i] - stack1[i]))
		return maximum


class Solution:

	def findMaxDiff(self, arr, n):
		(LS, stack) = ([0], [arr[0]])
		for i in range(1, n):
			if stack[-1] < arr[i]:
				LS.append(stack[-1])
			else:
				while stack and stack[-1] >= arr[i]:
					stack.pop()
				if not stack:
					LS.append(0)
				else:
					LS.append(stack[-1])
			stack.append(arr[i])
		(RS, stack) = ([0], [arr[-1]])
		for i in range(n - 2, -1, -1):
			if stack[-1] < arr[i]:
				RS.append(stack[-1])
			else:
				while stack and stack[-1] >= arr[i]:
					stack.pop()
				if not stack:
					RS.append(0)
				else:
					RS.append(stack[-1])
			stack.append(arr[i])
		RS = RS[::-1]
		ans = 0
		for i in range(n):
			ans = max(ans, abs(LS[i] - RS[i]))
		return ans


class Solution:

	def findMaxDiff(self, arr, n):
		l1 = []
		ls = []
		rs = []
		l1.append(arr[0])
		for i in range(n):
			while l1 and l1[-1] >= arr[i]:
				l1.pop()
			if len(l1) == 0:
				ls.append(0)
			elif l1[-1] < arr[i]:
				ls.append(l1[-1])
			l1.append(arr[i])
		l1 = []
		l1.append(arr[n - 1])
		for i in range(n - 1, -1, -1):
			while l1 and l1[-1] >= arr[i]:
				l1.pop()
			if len(l1) == 0:
				rs.append(0)
			elif l1[-1] < arr[i]:
				rs.append(l1[-1])
			l1.append(arr[i])
		rs = rs[::-1]
		max = 0
		for i in range(n):
			diff = abs(ls[i] - rs[i])
			if max < diff:
				max = diff
		return max


class Solution:

	def findMaxDiff(self, arr, n):
		min_left = 1000
		LS = []
		for i in range(len(arr)):
			if arr[i] <= min_left or i == 0:
				LS.append(0)
			else:
				for j in range(i - 1, -1, -1):
					if arr[j] < arr[i]:
						LS.append(arr[j])
						break
			if arr[i] < min_left:
				min_left = arr[i]
		min_right = 1000
		RS = []
		for i in range(len(arr) - 1, -1, -1):
			if arr[i] <= min_right or i == len(arr) - 1:
				RS.append(0)
			else:
				for j in range(i + 1, len(arr)):
					if arr[j] < arr[i]:
						RS.append(arr[j])
						break
			if arr[i] < min_right:
				min_right = arr[i]
		max_dif = 0
		for i in range(min(len(LS), len(RS))):
			dif = abs(LS[i] - RS[len(RS) - 1 - i])
			if dif > max_dif:
				max_dif = dif
		return max_dif


class Solution:

	def findMaxDiff(self, arr, n):
		ls = []
		for (i, v) in enumerate(arr):
			if i == 0:
				ls.append(0)
				continue
			else:
				prev = arr[i - 1]
				if prev < v:
					ls.append(prev)
				else:
					j = i - 1
					while j >= 0:
						if arr[j] < v:
							ls.append(arr[j])
							break
						j -= 1
					else:
						ls.append(0)
		rs = []
		for (i, v) in enumerate(arr):
			if i == n - 1:
				rs.append(0)
				break
			else:
				nex = arr[i + 1]
				if nex < v:
					rs.append(nex)
				else:
					j = i + 1
					while j < n:
						if arr[j] < v:
							rs.append(arr[j])
							break
						j += 1
					else:
						rs.append(0)
		m = 0
		for i in range(n):
			if abs(ls[i] - rs[i]) > m:
				m = abs(ls[i] - rs[i])
		return m


class Solution:

	def lsmall_elem(self, arr, n):
		lstack = [arr[0]]
		rstack = [arr[-1]]
		lsmall = [0 for _ in range(n)]
		rsmall = [0 for _ in range(n)]
		for i in range(1, n):
			while len(lstack) > 0 and lstack[-1] >= arr[i]:
				lstack.pop()
			while len(rstack) > 0 and rstack[-1] >= arr[-i - 1]:
				rstack.pop()
			if len(lstack) > 0:
				lsmall[i] = lstack[-1]
			if len(rstack) > 0:
				rsmall[-i - 1] = rstack[-1]
			lstack.append(arr[i])
			rstack.append(arr[-i - 1])
		return (lsmall, rsmall)

	def findMaxDiff(self, arr, n):
		(lsmall, rsmall) = self.lsmall_elem(arr, n)
		max_diff = 0
		for i in range(n):
			max_diff = max(max_diff, abs(lsmall[i] - rsmall[i]))
		return max_diff


class Solution:

	def findMaxDiff(self, arr, n):
		st = []
		l = []
		for i in arr:
			while st and st[-1] >= i:
				st.pop()
			if st:
				l.append(st[-1])
			else:
				l.append(0)
			st.append(i)
		st = []
		r = []
		for i in arr[::-1]:
			while st and st[-1] >= i:
				st.pop()
			if st:
				r.append(st[-1])
			else:
				r.append(0)
			st.append(i)
		ans = 0
		r = r[::-1]
		for i in range(n):
			ans = max(ans, abs(l[i] - r[i]))
		return ans


class Solution:

	def findMaxDiff(self, arr, n):
		left = []
		stack = []
		for item in arr:
			while stack and stack[-1] >= item:
				stack.pop()
			if stack:
				left.append(stack[-1])
			else:
				left.append(0)
			stack.append(item)
		right = []
		stack = []
		for item in arr[::-1]:
			while stack and stack[-1] >= item:
				stack.pop()
			if stack:
				right.append(stack[-1])
			else:
				right.append(0)
			stack.append(item)
		result = 0
		for i in range(n):
			result = max(result, abs(right[i] - left[-i - 1]))
		return result


class Solution:

	def findMaxDiff(self, arr, n):
		ls = []
		stack = [0]
		rs = []
		maxa = 0
		k = 0
		rst = [0]
		for i in arr:
			if stack[-1] >= i:
				while stack[-1] >= i:
					stack.pop()
			if stack[-1] < i:
				ls.append(stack[-1])
			stack.append(i)
		for i in arr[::-1]:
			if i <= rst[-1]:
				while i <= rst[-1]:
					rst.pop()
			if i > rst[-1]:
				rs.append(rst[-1])
			rst.append(i)
		rs = rs[::-1]
		for i in range(len(ls)):
			maxa = max(maxa, abs(ls[i] - rs[i]))
		return maxa


class Solution:

	def leftsmaller(self, arr, n, SE):
		sta = []
		for i in range(n):
			while sta != [] and sta[len(sta) - 1] >= arr[i]:
				sta.pop()
			if sta != []:
				SE[i] = sta[len(sta) - 1]
			else:
				SE[i] = 0
			sta.append(arr[i])

	def findMaxDiff(self, arr, n):
		ls = [0] * n
		rs = [0] * n
		self.leftsmaller(arr, n, ls)
		self.leftsmaller(arr[::-1], n, rs)
		res = -1
		for i in range(n):
			res = max(res, abs(ls[i] - rs[n - 1 - i]))
		return res


class Solution:

	def findMaxDiff(self, arr, n):
		left = []
		stack = []
		for item in arr:
			while stack and stack[-1] >= item:
				stack.pop()
			i = 0
			value = 0
			while i < len(stack):
				if stack[-i - 1] < item:
					value = stack[-i - 1]
					break
				i += 1
			left.append(value)
			stack.append(item)
		right = []
		stack = []
		for item in arr[::-1]:
			while stack and stack[-1] >= item:
				stack.pop()
			i = 0
			value = 0
			while i < len(stack):
				if stack[-i - 1] < item:
					value = stack[-i - 1]
					break
				i += 1
			right.append(value)
			stack.append(item)
		right.reverse()
		result = 0
		for i in range(n):
			result = max(result, abs(right[i] - left[i]))
		return result


class Solution:

	def findMaxDiff(self, arr, n):
		stack = [0, arr[0]]
		list1 = []
		for i in range(n):
			if i == 0:
				list1.append(0)
			else:
				while stack != []:
					if stack[-1] < arr[i]:
						list1.append(stack[-1])
						stack.append(arr[i])
						break
					else:
						stack.pop()
		stack = [0, arr[-1]]
		list2 = [0] * n
		for j in range(-1, -n - 1, -1):
			if j == -1:
				list2[j] = 0
			else:
				while stack != []:
					if stack[-1] < arr[j]:
						list2[j] = stack[-1]
						stack.append(arr[j])
						break
					else:
						stack.pop()
		maximum = -1
		for i in range(n):
			maximum = max(maximum, abs(list1[i] - list2[i]))
		return maximum


class Solution:

	def findMaxDiff(self, a, n):
		a1 = a[::-1]
		stack = []
		b = []
		i = 0
		d = []
		while i < n:
			if len(stack) != 0:
				if stack[-1] < a[i]:
					b.append(stack[-1])
					stack.append(a[i])
					i = i + 1
				else:
					stack.pop()
			else:
				stack.append(a[i])
				b.append(0)
				i = i + 1
		i1 = 0
		stack1 = []
		b1 = []
		while i1 < n:
			if len(stack1) != 0:
				if stack1[-1] < a1[i1]:
					b1.append(stack1[-1])
					stack1.append(a1[i1])
					i1 = i1 + 1
				else:
					stack1.pop()
			else:
				stack1.append(a1[i1])
				b1.append(0)
				i1 = i1 + 1
		r = b1[::-1]
		for i in range(0, n):
			d.append(abs(b[i] - r[i]))
		return max(d)


class Solution:

	def findMaxDiff(self, arr, n):
		l = []
		r = []
		stack = []
		for i in range(n):
			while stack and arr[i] <= stack[-1]:
				stack.pop()
			if not stack:
				l.append(0)
			else:
				l.append(stack[-1])
			stack.append(arr[i])
		stack.clear()
		for i in range(n - 1, -1, -1):
			while stack and arr[i] <= stack[-1]:
				stack.pop()
			if not stack:
				r.insert(0, 0)
			else:
				r.insert(0, stack[-1])
			stack.append(arr[i])
		res = 0
		for i in range(n):
			res = max(res, abs(l[i] - r[i]))
		return res


class Solution:

	def findMaxDiff(self, arr, n):
		n = len(arr)
		r = [0] * n
		l = [0] * n
		s = []
		for i in range(n):
			while s != [] and arr[s[-1]] > arr[i]:
				tmp = s.pop()
				r[tmp] = arr[i]
			s.append(i)
		s = []
		for i in range(n - 1, -1, -1):
			while s != [] and arr[s[-1]] > arr[i]:
				tmp = s.pop()
				l[tmp] = arr[i]
			s.append(i)
		maxi = float('-inf')
		for i in range(n):
			val = abs(r[i] - l[i])
			if val > maxi:
				maxi = val
		return maxi


def leftmin(arr, n):
	s = []
	left = []
	for i in range(n):
		while len(s) != 0 and s[-1] >= arr[i]:
			s.pop()
		if len(s) == 0:
			left.append(0)
		else:
			left.append(s[-1])
		s.append(arr[i])
	return left

def rightmax(arr, n):
	st = []
	right = [0 for i in range(n)]
	for i in range(n - 1, -1, -1):
		while len(st) != 0 and st[-1] >= arr[i]:
			st.pop()
		if len(st) == 0:
			right[i] = 0
		else:
			right[i] = st[-1]
		st.append(arr[i])
	return right

class Solution:

	def findMaxDiff(self, arr, n):
		l = leftmin(arr, n)
		r = rightmax(arr, n)
		m = 0
		for i in range(0, n):
			m = max(m, abs(l[i] - r[i]))
		return m


class Solution:

	def findMaxDiff(self, arr, n):
		diff = 0
		for (pos, i) in enumerate(arr):
			l = 0
			r = 0
			for rpointer in range(pos + 1, n):
				if arr[rpointer] < i:
					r = arr[rpointer]
					break
			for lpointer in range(pos - 1, -1, -1):
				if arr[lpointer] < i:
					l = arr[lpointer]
					break
			tempDiff = abs(l - r)
			if tempDiff > diff:
				diff = tempDiff
		return diff


class Solution:

	def findMaxDiff(self, arr, n):
		LS = [0] * n
		RS = [0] * n
		for i in range(n):
			min_ = arr[i]
			for j in range(i + 1, n, 1):
				if arr[j] < min_:
					min_ = arr[j]
					break
			if min_ != arr[i]:
				LS[i] = min_
		for i in range(n - 1, -1, -1):
			min_ = arr[i]
			for j in range(i - 1, -1, -1):
				if arr[j] < min_:
					min_ = arr[j]
					break
			if min_ != arr[i]:
				RS[i] = min_
		max_sum = abs(LS[0] - RS[0])
		for i in range(1, n, 1):
			if abs(LS[i] - RS[i]) > max_sum:
				max_sum = abs(LS[i] - RS[i])
		return max_sum


class Solution:

	def findMaxDiff(self, arr, n):

		def NSR(arr):
			stck = []
			N = []
			i = len(arr) - 1
			while i > -1:
				if len(stck) == 0:
					N.append(0)
					stck.append(arr[i])
					i -= 1
				elif stck[-1] < arr[i]:
					N.append(stck[-1])
					stck.append(arr[i])
					i -= 1
				else:
					stck.pop()
			return N[::-1]

		def NSL(arr):
			stck = []
			i = 0
			N = []
			while i < len(arr):
				if len(stck) == 0:
					N.append(0)
					stck.append(arr[i])
					i += 1
				elif stck[-1] < arr[i]:
					N.append(stck[-1])
					stck.append(arr[i])
					i += 1
				else:
					stck.pop()
			return N
		maxx = -1
		Right = NSR(arr)
		lef = NSL(arr)
		for i in range(len(arr)):
			maxx = max(abs(Right[i] - lef[i]), maxx)
		return maxx


class Solution:

	def findMaxDiff(self, arr, n):
		LS = findSmaller(arr)
		RS = list(reversed(findSmaller(list(reversed(arr)))))
		max_diff = 0
		for k in range(n):
			diff = abs(LS[k] - RS[k])
			if diff > max_diff:
				max_diff = diff
		return max_diff

def findSmaller(arr):
	Smallers = [0] * len(arr)
	s = Stack()
	for i in range(len(arr)):
		while not s.is_empty() and s.peek() >= arr[i]:
			s.pop()
		if not s.is_empty():
			Smallers[i] = s.peek()
		s.push(arr[i])
	return Smallers

class Stack:

	def __init__(self):
		self._values = []

	def push(self, elem):
		self._values.append(elem)

	def is_empty(self):
		return self._values == []

	def pop(self):
		return self._values.pop()

	def peek(self):
		return self._values[-1]


class Solution:

	def findMaxDiff(self, arr, n):
		l = [0 for x in arr]
		r = [0 for x in arr]
		for i in range(n):
			k = i - 1
			flag = 0
			while k >= 0:
				if arr[k] >= arr[i]:
					k -= 1
				else:
					l[i] = arr[k]
					flag = 1
					break
			if flag != 1:
				l[i] = 0
		for i in range(n):
			k = i + 1
			flag = 0
			while k < n:
				if arr[k] >= arr[i]:
					k += 1
				else:
					r[i] = arr[k]
					flag = 1
					break
			if flag != 1:
				r[i] = 0
		res = 0
		for i in range(n):
			if res < abs(l[i] - r[i]):
				res = abs(l[i] - r[i])
		return res


class Solution:

	def findMaxDiff(self, arr, n):
		LS = [0] * n
		RS = [0] * n
		answer = 0
		for i in range(len(arr)):
			for j in reversed(arr[:i]):
				if j < arr[i]:
					LS[i] = j
					break
			for k in arr[i:]:
				if k < arr[i]:
					RS[i] = k
					break
			if abs(LS[i] - RS[i]) > answer:
				answer = abs(LS[i] - RS[i])
		return answer


class Solution:

	def findMaxDiff(self, arr, n):
		l = []
		r = []
		for i in range(len(arr)):
			ans = 0
			for j in range(i, -1, -1):
				if arr[j] < arr[i]:
					ans = arr[j]
					break
			l.append(ans)
		for i in range(len(arr)):
			ans = 0
			for j in range(i, len(arr)):
				if arr[j] < arr[i]:
					ans = arr[j]
					break
			r.append(ans)
		maxi = 0
		for i in range(len(l)):
			my = abs(l[i] - r[i])
			if my > maxi:
				maxi = my
		return maxi


class Solution:

	def findMaxDiff(self, arr, n):
		left_smaller = [0] * n
		right_smaller = [0] * n
		stack = [0]
		for i in range(1, n):
			if len(stack) == 0 or arr[stack[-1]] <= arr[i]:
				stack.append(i)
			else:
				while stack and arr[stack[-1]] > arr[i]:
					left_smaller[stack[-1]] = arr[i]
					stack.pop()
				stack.append(i)
		stack = [n - 1]
		for i in range(n - 2, -1, -1):
			if len(stack) == 0 or arr[stack[-1]] <= arr[i]:
				stack.append(i)
			else:
				while stack and arr[stack[-1]] > arr[i]:
					right_smaller[stack[-1]] = arr[i]
					stack.pop()
				stack.append(i)
		max_diff = float('-inf')
		for i in range(n):
			if abs(left_smaller[i] - right_smaller[i]) > max_diff:
				max_diff = abs(left_smaller[i] - right_smaller[i])
		return max_diff


class Solution:

	def findMaxDiff(self, arr, n):
		larr = arr[:]
		larr.insert(0, 0)
		rarr = arr[:]
		rarr.append(0)
		LS = []
		RS = []
		for i in range(len(larr)):
			curr = larr[i]
			for l in range(i, -1, -1):
				if larr[l] < larr[i]:
					LS.append(larr[l])
					break
		for i in range(len(rarr)):
			curr = rarr[i]
			for l in range(i, len(rarr)):
				if rarr[l] < rarr[i]:
					RS.append(rarr[l])
					break
		diffs = [abs(LS[i] - RS[i]) for i in range(len(LS))]
		return max(diffs)


class Solution:

	def findMaxDiff(self, arr, n):
		ls = []
		rs = []
		for (i, val) in enumerate(arr):
			for j in arr[:i][::-1]:
				if j < val:
					ls.append(j)
					break
			else:
				ls.append(0)
		for (i, val) in enumerate(arr):
			for j in arr[i:]:
				if j < val:
					rs.append(j)
					break
			else:
				rs.append(0)
		mx = -float('inf')
		for (l, r) in zip(ls, rs):
			mx = max(mx, abs(l - r))
		return mx


class Solution:

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

	def NSR(self, arr, n):
		stack = []
		result = []
		for i in range(n - 1, -1, -1):
			if len(stack) == 0:
				result.append(0)
			elif len(stack) > 0 and stack[-1] < arr[i]:
				result.append(stack[-1])
			else:
				while len(stack) > 0 and stack[-1] >= arr[i]:
					stack.pop()
				if len(stack) == 0:
					result.append(0)
				else:
					result.append(stack[-1])
			stack.append(arr[i])
		result.reverse()
		return result

	def findMaxDiff(self, arr, n):
		left = self.NSL(arr, n)
		right = self.NSR(arr, n)
		maxi = 0
		for i in range(n):
			jk = abs(left[i] - right[i])
			maxi = max(maxi, jk)
		return maxi


class Solution:

	def findMaxDiff(self, arr, n):
		from collections import deque
		a = deque()
		left = [0]
		l = []
		i = 0
		while i < n:
			while left[-1] >= arr[i]:
				left.pop()
			l.append(left[-1])
			left.append(arr[i])
			i += 1
		r = []
		right = [0]
		i = n - 1
		while i >= 0:
			while right[-1] >= arr[i]:
				right.pop()
			r.append(right[-1])
			right.append(arr[i])
			i -= 1
		rr = r[::-1]
		ans = 0
		for i in range(len(l)):
			m = abs(l[i] - rr[i])
			ans = max(ans, m)
		return ans


class Solution:

	def findMaxDiff(self, arr, n):

		def find_smallest(arr):
			i = 0
			stack = []
			output = []
			while i < len(arr):
				if len(stack) == 0:
					output.append(0)
					stack.append(arr[i])
					i += 1
				elif stack[-1] < arr[i]:
					output.append(stack[-1])
					stack.append(arr[i])
					i += 1
				else:
					stack.pop()
			return output
		left = find_smallest(arr)
		arr.reverse()
		right = find_smallest(arr)
		right.reverse()
		max_res = 0
		for (l, r) in zip(left, right):
			max_res = max(max_res, abs(l - r))
		return max_res


class Solution:

	def findMaxDiff(self, arr, n):
		LS = [0] * n
		st = []
		for i in range(n):
			while len(st) != 0 and st[-1] >= arr[i]:
				st.pop()
			if len(st) != 0:
				LS[i] = st[-1]
			st.append(arr[i])
		RS = [0] * n
		st = []
		for i in range(n - 1, -1, -1):
			while len(st) != 0 and st[-1] >= arr[i]:
				st.pop()
			if len(st) != 0:
				RS[i] = st[-1]
			st.append(arr[i])
		ans = -1
		for i in range(n):
			ans = max(ans, abs(RS[i] - LS[i]))
		return ans


class Solution:

	def findMaxDiff(self, arr, n):
		ls = []
		rs = []
		minn = 9999999
		for i in range(n):
			ls_element = 0
			for j in range(i - 1, -1, -1):
				if arr[j] < arr[i]:
					ls_element = arr[j]
					break
			rs_element = 0
			for j in range(i + 1, n, 1):
				if arr[j] < arr[i]:
					rs_element = arr[j]
					break
			ls.append(ls_element)
			rs.append(rs_element)
		abs_diff = []
		for i in range(n):
			abs_diff.append(abs(ls[i] - rs[i]))
		return max(abs_diff)


class Solution:

	def findMaxDiff(self, arr, n):
		left_smaller = []
		right_smaller = []
		for i in range(n):
			left_smaller_element = 0
			for j in range(i - 1, -1, -1):
				if arr[j] < arr[i]:
					left_smaller_element = arr[j]
					break
			right_smaller_element = 0
			for j in range(i + 1, n, 1):
				if arr[j] < arr[i]:
					right_smaller_element = arr[j]
					break
			left_smaller.append(left_smaller_element)
			right_smaller.append(right_smaller_element)
		abs_differences = []
		for i in range(n):
			abs_differences.append(abs(left_smaller[i] - right_smaller[i]))
		return max(abs_differences)


class Solution:

	def findMaxDiff(self, arr, n):
		Ls = [0] * len(arr)
		Rs = [0] * len(arr)
		Ls[0] = 0
		Rs[-1] = 0
		for i in range(1, len(arr)):
			for j in range(i - 1, -1, -1):
				if arr[j] < arr[i]:
					Ls[i] = arr[j]
					break
		for i in range(len(arr) - 1):
			for j in range(i + 1, len(arr)):
				if arr[j] < arr[i]:
					Rs[i] = arr[j]
					break
		maxim = 0
		for i in range(len(arr)):
			diff = abs(Ls[i] - Rs[i])
			maxim = max(diff, maxim)
		return maxim


class Solution:

	def findMaxDiff(self, a, n):
		s = [n - 1]
		c = [0]
		for i in range(n - 2, -1, -1):
			while len(s) != 0 and a[s[-1]] >= a[i]:
				s.pop()
			if len(s) == 0:
				c.append(0)
			else:
				c.append(a[s[-1]])
			s.append(i)
		c.reverse()
		s.clear()
		s = [0]
		o = [0]
		for i in range(1, n):
			while len(s) != 0 and a[s[-1]] >= a[i]:
				s.pop()
			if len(s) == 0:
				o.append(0)
			else:
				o.append(a[s[-1]])
			s.append(i)
		m = 0
		for i in range(n):
			m = max(m, abs(o[i] - c[i]))
		return m


class Solution:

	def findMaxDiff(self, arr, n):
		LS = []
		RS = []
		stack = []
		diff = 0
		for element in arr:
			if len(stack) == 0:
				LS.append(0)
				stack.append(element)
			else:
				while len(stack) > 0 and stack[len(stack) - 1] >= element:
					stack.pop()
				if len(stack) == 0:
					LS.append(0)
					stack.append(element)
				elif stack[len(stack) - 1] < element:
					LS.append(stack[len(stack) - 1])
					stack.append(element)
		stack.clear()
		for index in range(n - 1, -1, -1):
			if len(stack) == 0:
				RS.append(0)
				stack.append(arr[index])
			else:
				while len(stack) > 0 and stack[len(stack) - 1] >= arr[index]:
					stack.pop()
				if len(stack) == 0:
					RS.append(0)
					stack.append(arr[index])
				elif stack[len(stack) - 1] < arr[index]:
					RS.append(stack[len(stack) - 1])
					stack.append(arr[index])
		RS.reverse()
		diff = []
		for index in range(0, n):
			diff.append(abs(LS[index] - RS[index]))
		return max(diff)


class Solution:

	def findMaxDiff(self, arr, n):

		def stackO(arr, n):
			s = []
			l = [0 for i in range(n)]
			i = 0
			while i < n:
				if len(s) == 0:
					s.append(i)
					i += 1
				else:
					while len(s) > 0 and arr[s[-1]] > arr[i]:
						l[s[-1]] = arr[i]
						del s[-1]
					s.append(i)
					i += 1
			while len(s) > 0:
				l[s[-1]] = 0
				del s[-1]
			return l
		ls = []
		rs = stackO(arr, n)
		t = arr
		t.reverse()
		ls = stackO(t, n)
		ls.reverse()
		diff = 0
		for i in range(n):
			diff = max(diff, abs(ls[i] - rs[i]))
		return diff


from collections import deque

class Solution:

	def findMaxDiff(self, arr, n):
		(ql, qr) = (deque(), deque())
		ls = [0 for i in range(n)]
		rs = [0 for i in range(n)]
		for i in range(n):
			while ql and arr[ql[-1]] > arr[i]:
				ls[ql.pop()] = arr[i]
			ql.append(i)
		for i in range(n - 1, -1, -1):
			while qr and arr[qr[-1]] > arr[i]:
				rs[qr.pop()] = arr[i]
			qr.append(i)
		maxDiff = -float('inf')
		for i in range(n):
			maxDiff = max(maxDiff, abs(ls[i] - rs[i]))
		return maxDiff


class Solution:

	def findMaxDiff(self, arr, n):
		n = len(arr)
		if n == 0:
			return 0
		st = [0]
		lt = [0 for i in range(n)]
		rt = [0 for i in range(n)]
		md = 0
		for i in range(1, n):
			if arr[i] > arr[st[-1]]:
				lt[i] = arr[st[-1]]
				st.append(i)
			else:
				while st and arr[st[-1]] > arr[i]:
					rt[st[-1]] = arr[i]
					x = st.pop(-1)
				if st and arr[st[-1]] < arr[i]:
					lt[i] = arr[st[-1]]
				if st and arr[st[-1]] == arr[i]:
					lt[i] = lt[st[-1]]
				st.append(i)
		while st:
			temp = st[-1]
			st.pop(-1)
			rt[temp] = 0
		for i in range(n):
			md = max(md, abs(lt[i] - rt[i]))
		return md


import sys

class Solution:

	def findMaxDiff(self, arr, n):
		a = self.nsl(arr, n)
		b = self.nsr(arr, n)
		maxi = -sys.maxsize
		for i in range(0, n):
			if abs(a[i] - b[i]) > maxi:
				maxi = abs(a[i] - b[i])
		return maxi

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

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


class Solution:

	def findMaxDiff(self, arr, n):
		s1 = []
		s2 = []
		ans = [0] * n
		ans1 = [0] * n
		for i in range(n - 1, -1, -1):
			while s1 and arr[i] <= s1[-1]:
				s1.pop()
			if len(s1) == 0:
				ans[i] = 0
			else:
				ans[i] = s1[-1]
			s1.append(arr[i])
		for j in range(n):
			while s2 and arr[j] <= s2[-1]:
				s2.pop()
			if len(s2) == 0:
				ans1[j] = 0
			else:
				ans1[j] = s2[-1]
			s2.append(arr[j])
		maxi = 0
		for k in range(n):
			maxi = max(maxi, abs(ans1[k] - ans[k]))
		return maxi


class Solution:

	def findMaxDiff(self, arr, n):
		ls = [0] * n
		rs = [0] * n
		stack = []
		for (i, val) in enumerate(arr):
			while stack and stack[-1] >= val:
				stack.pop()
			if stack:
				ls[i] = stack[-1]
			stack.append(val)
		while stack:
			stack.pop()
		for i in range(n - 1, -1, -1):
			val = arr[i]
			while stack and stack[-1] >= val:
				stack.pop()
			if stack:
				rs[i] = stack[-1]
			stack.append(val)
		res = 0
		for i in range(n):
			res = max(res, abs(ls[i] - rs[i]))
		return res


class Solution:

	def findMaxDiff(self, arr, n):
		ls = [0] * n
		rs = [0] * n
		stack = []
		for i in range(n):
			while len(stack) != 0 and stack[0] >= arr[i]:
				stack.pop(0)
			if len(stack) != 0:
				ls[i] = stack[0]
				stack.insert(0, arr[i])
			else:
				ls[i] = 0
				stack.insert(0, arr[i])
		stack = []
		for i in range(n - 1, -1, -1):
			while len(stack) != 0 and stack[-1] >= arr[i]:
				stack.pop(-1)
			if len(stack) != 0:
				rs[i] = stack[-1]
				stack.append(arr[i])
			else:
				rs[i] = 0
				stack.append(arr[i])
		maxi = 0
		for i in range(n):
			diff = abs(ls[i] - rs[i])
			if diff > maxi:
				maxi = diff
		return maxi


class Solution:

	def findMaxDiff(self, arr, n):
		stack = []
		k = 0
		while k <= n - 1:
			ap = 0
			flag = 0
			slag = 0
			z = -1
			if k == 0:
				for i in range(n):
					if arr[i] < arr[k]:
						z = arr[i]
						break
				if z != -1:
					ap = abs(z - 0)
			elif k == n - 1:
				for i in range(k, -1, -1):
					if arr[k] > arr[i]:
						z = arr[i]
						break
				if z != -1:
					ap = abs(z - 0)
			else:
				for i in range(k - 1, -1, -1):
					if arr[k] > arr[i]:
						L = arr[i]
						flag = 1
						break
				for j in range(k, n):
					if arr[k] > arr[j]:
						R = arr[j]
						slag = 1
						break
				if flag == 1 and slag == 1:
					ap = abs(R - L)
			if len(stack) != 0:
				if stack[-1] <= ap:
					stack.pop()
					stack.append(ap)
			else:
				stack.append(ap)
			k += 1
		return stack[0]


class Solution:

	def prevSmaller(self, arr, n):
		prev = [0] * n
		st = []
		for i in range(n):
			while len(st) > 0 and st[-1] >= arr[i]:
				st.pop()
			if len(st) > 0:
				prev[i] = st[-1]
			else:
				prev[i] = 0
			st.append(arr[i])
		return prev

	def nextSmaller(self, arr, n):
		next_ = [0] * n
		st = []
		for i in range(n - 1, -1, -1):
			while len(st) > 0 and st[-1] >= arr[i]:
				st.pop()
			if len(st) > 0:
				next_[i] = st[-1]
			else:
				next_[i] = 0
			st.append(arr[i])
		return next_

	def findMaxDiff(self, arr, n):
		a1 = self.prevSmaller(arr, n)
		a2 = self.nextSmaller(arr, n)
		max_diff = 0
		for i in range(n):
			max_diff = max(max_diff, abs(a1[i] - a2[i]))
		return max_diff