Given an unsorted array Arr of size N. Find the subarray Arr[s...e] such that sorting this subarray makes the whole array sorted.
Example 1:
Input:
N = 11
Arr[] ={10,12,20,30,25,40,32,31,35,50,60}
Output: 3 8
Explanation: Subarray starting from index
3 and ending at index 8 is required
subarray. Initial array: 10 12 20 30 25
40 32 31 35 50 60 Final array: 10 12 20
25 30 31 32 35 40 50 60
(After sorting the bold part)
Example 2:
Input:
N = 9
Arr[] = {0, 1, 15, 25, 6, 7, 30, 40, 50}
Output: 2 5
Explanation: Subarray starting from index
2 and ending at index 5 is required
subarray.
Initial array: 0 1 15 25 6 7 30 40 50
Final array:   0 1 6 7 15 25 30 40 50
(After sorting the bold part)
Your Task:
You don't need to read input or print anything. Your task is to complete the function printUnsorted() which takes the array of integers arr and n as parameters and returns a pair of integers denoting {s, e}. If no such subarray exists, return {0, 0}.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{7}
1 ≤ Arr[i] ≤ 10^{8}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3

class Solution:



	def printUnsorted(self,arr, n):

		# code here

Solutions:
class Solution:

	def printUnsorted(self, arr, n):
		l = arr[:]
		l.sort()
		if n == 1:
			x = [0, 0]
			return x
		else:
			for i in range(n):
				if l[i] != arr[i]:
					a = i
					break
			for j in range(n - 1, -1, -1):
				if l[j] != arr[j]:
					b = j
					break
			x = [a, b]
			return x


class Solution:

	def printUnsorted(self, arr, n):
		sorted_arr = arr.copy()
		res = []
		sorted_arr.sort()
		for i in range(n):
			if arr[i] != sorted_arr[i]:
				res.append(i)
				break
		arr.reverse()
		sorted_arr.reverse()
		for i in range(n):
			if arr[i] != sorted_arr[i]:
				res.append(n - i - 1)
				break
		if res == []:
			return [0, 0]
		return res


class Solution:

	def printUnsorted(self, arr, n):
		t = arr[:]
		t.sort()
		(s, e) = (0, 0)
		for i in range(n):
			if arr[i] != t[i]:
				s = i
				break
		for i in range(n - 1, -1, -1):
			if arr[i] != t[i]:
				e = i
				break
		return [s, e]


class Solution:

	def printUnsorted(self, arr, n):
		if n == 1:
			return [0, 0]
		i = 0
		j = n - 1
		start = 0
		end = 0
		ans = []
		while i < n - 1:
			if arr[i + 1] < arr[i]:
				start = i
				break
			i += 1
		while j > 0:
			if arr[j - 1] > arr[j]:
				end = j
				break
			j -= 1
		mini = min(arr[start:end + 1])
		maxi = max(arr[start:end + 1])
		for i in range(n):
			if arr[i] > mini:
				ans.append(i)
				break
		for i in range(n - 1, -1, -1):
			if arr[i] < maxi:
				ans.append(i)
				break
		return ans


class Solution:

	def printUnsorted(self, arr, n):
		sarr = sorted(arr)
		(s, e) = (n, -1)
		for i in range(n):
			if sarr[i] != arr[i]:
				s = min(s, i)
				e = max(e, i)
		if s == n:
			return (0, 0)
		else:
			return (s, e)


class Solution:

	def printUnsorted(self, a, n):
		l = a.copy()
		l.sort()
		if n == 1:
			return (0, 0)
		for i in range(n):
			if l[i] != a[i]:
				k = i
				break
		for j in range(n - 1, -1, -1):
			if l[j] != a[j]:
				k1 = j
				break
		return (k, k1)


class Solution:

	def printUnsorted(self, arr, n):
		lis = arr.copy()
		lis.sort()
		if n == 1:
			return (0, 0)
		for i in range(n):
			if lis[i] != arr[i]:
				k = i
				break
		for j in range(n - 1, -1, -1):
			if lis[j] != arr[j]:
				k1 = j
				break
		return (k, k1)


class Solution:

	def printUnsorted(self, arr, n):
		(start, end) = (0, n - 1)
		max_till_now = -float('inf')
		min_till_now = float('inf')
		for i in range(n):
			if arr[i] < max_till_now:
				end = i
			max_till_now = max(max_till_now, arr[i])
			if arr[n - i - 1] > min_till_now:
				start = n - i - 1
			min_till_now = min(min_till_now, arr[n - i - 1])
		return [start, end]


class Solution:

	def printUnsorted(self, arr, n):
		smallest = 0
		largest = 0
		smallest_arr = [0] * n
		largest_arr = [0] * n
		smallest_arr[n - 1] = arr[n - 1]
		for i in range(n - 2, -1, -1):
			if arr[i] < smallest_arr[i + 1]:
				smallest_arr[i] = arr[i]
			else:
				smallest_arr[i] = smallest_arr[i + 1]
		largest_arr[0] = arr[0]
		for j in range(1, n):
			if arr[j] > largest_arr[j - 1]:
				largest_arr[j] = arr[j]
			else:
				largest_arr[j] = largest_arr[j - 1]
		for i in range(n):
			if arr[i] > smallest_arr[i]:
				smallest = i
				break
		for j in range(n - 1, -1, -1):
			if arr[j] < largest_arr[j]:
				largest = j
				break
		return (smallest, largest)


class Solution:

	def printUnsorted(self, arr, n):

		def sol1():
			(start, end) = (-1, 0)
			sortedArr = sorted(arr)
			for (i, num) in enumerate(arr):
				if sortedArr[i] != num and start == -1:
					start = i
				elif sortedArr[i] != num:
					end = i
			if start == -1:
				start = 0
			return (start, end)

		def sol2():
			(minV, maxV) = (arr[0], arr[0])
			(start, end) = (n, 0)
			i = 1
			while i < n:
				if arr[i] >= maxV:
					maxV = arr[i]
				else:
					end = i
					if start > 0:
						temp = start
						if start == n:
							temp = end - 1
							minV = arr[temp]
						while temp > -1:
							if minV <= arr[i]:
								start = min(temp + 1, start)
								minV = arr[start]
								break
							if temp == 0 and minV > arr[i]:
								start = 0
								break
							temp -= 1
							minV = arr[temp]
				i += 1
			if start == n:
				start = 0
			return (start, end)
		return sol2()


class Solution:

	def printUnsorted(self, arr, n):
		(start, end) = (-1, 0)
		sortedArr = sorted(arr)
		for (i, num) in enumerate(arr):
			if sortedArr[i] != num and start == -1:
				start = i
			elif sortedArr[i] != num:
				end = i
		if start == -1:
			start = 0
		return (start, end)


class Solution:

	def printUnsorted(self, arr, n):
		left = 0
		right = 0
		curr = -float('inf')
		for i in range(0, n):
			curr = max(curr, arr[i])
			if arr[i] < curr:
				right = i
		curr = float('inf')
		for i in range(n - 1, -1, -1):
			curr = min(curr, arr[i])
			if arr[i] > curr:
				left = i
		return [left, right]


class Solution:

	def printUnsorted(self, arr, n):
		b = sorted(arr)
		l = []
		for i in range(len(arr)):
			if arr[i] != b[i]:
				l.append(i)
				break
		for j in range(len(arr) - 1, -1, -1):
			if arr[j] != b[j]:
				l.append(j)
				break
		if len(arr) == 1:
			return [0, 0]
		else:
			return l


class Solution:

	def printUnsorted(self, arr, n):
		l = sorted(arr)
		if arr == l:
			return [0, 0]
		p = []
		if l[0] != arr[0] and l[-1] != arr[-1]:
			return [0, n - 1]
		for i in range(n):
			if l[i] != arr[i]:
				p.append(i)
				break
		for i in range(n - 1, -1, -1):
			if l[i] != arr[i]:
				p.append(i)
				break
		return p


class Solution:

	def printUnsorted(self, nums, n):
		left = 9999999
		right = 0
		if nums == sorted(nums):
			return [0, 0]
		for (i, no) in enumerate(sorted(nums)):
			if nums[i] != no:
				left = min(i, left)
				right = max(i, right)
		return [left, right]


class Solution:

	def printUnsorted(self, arr, n):
		arr2 = []
		for e in arr:
			arr2.append(e)
		arr2.sort()
		s = 0
		e = 0
		for i in range(0, n):
			e1 = arr[i]
			e2 = arr2[i]
			if e1 != e2:
				s = i
				b1 = True
				break
		for i in range(0, n):
			e1 = arr[n - i - 1]
			e2 = arr2[n - i - 1]
			if e1 != e2:
				e = n - i - 1
				break
		return [s, e]


class Solution:

	def printUnsorted(self, arr, n):
		(curr_max, right_most, curr_min, left_most) = (0, 0, float('inf'), 0)
		for i in range(n):
			curr_max = max(arr[i], curr_max)
			if arr[i] < curr_max:
				right_most = i
			curr_min = min(arr[n - i - 1], curr_min)
			if arr[n - i - 1] > curr_min:
				left_most = n - i - 1
		return (left_most, right_most)


class Solution:

	def printUnsorted(self, a, n):
		(l, r) = (0, 0)
		least = float('inf')
		for i in range(n - 1, -1, -1):
			least = min(least, a[i])
			if least != a[i]:
				l = i
		mxm = float('-inf')
		for i in range(n):
			mxm = max(mxm, a[i])
			if mxm != a[i]:
				r = i
		return [l, r]


class Solution:

	def printUnsorted(self, arr, n):
		if n == 1:
			ans = [0, 0]
			return ans
		l = []
		ans = []
		for i in arr:
			l.append(i)
		l.sort()
		for i in range(n):
			if l[i] != arr[i]:
				ans.append(i)
				break
		for i in range(n - 1, -1, -1):
			if arr[i] != l[i]:
				ans.append(i)
				break
		return ans


class Solution:

	def printUnsorted(self, arr, n):
		if n == 1:
			return (0, 0)
		Max = -float('inf')
		Min = float('inf')
		for i in range(n):
			if i == 0:
				if arr[i] > arr[i + 1]:
					Min = min(Min, arr[i])
					Max = max(Max, arr[i])
			elif i == n - 1:
				if arr[i] < arr[i - 1]:
					Min = min(Min, arr[i])
					Max = max(Max, arr[i])
			elif arr[i] > arr[i + 1] or arr[i] < arr[i - 1]:
				Min = min(Min, arr[i])
				Max = max(Max, arr[i])
		start = 0
		while start < n and arr[start] <= Min:
			start += 1
		end = n - 1
		while end >= 0 and arr[end] >= Max:
			end -= 1
		if Max == -float('inf') or Min == float('inf'):
			return (0, 0)
		return (start, end)


import sys

class Solution:

	def isOutOfOrder(self, arr, i):
		if i == 0:
			return arr[i] > arr[i + 1]
		elif i == len(arr) - 1:
			return arr[i - 1] > arr[i]
		else:
			return arr[i] < arr[i - 1] or arr[i] > arr[i + 1]

	def printUnsorted(self, arr, n):
		ans = []
		if len(arr) == 1:
			ans.append(0)
			ans.append(0)
			return ans
		(mini, maxi) = (sys.maxsize, 0)
		for i in range(len(arr)):
			if self.isOutOfOrder(arr, i):
				mini = min(mini, arr[i])
				maxi = max(maxi, arr[i])
		if mini == sys.maxsize and maxi == 0:
			ans.append(0)
			ans.append(0)
			return ans
		else:
			i = 0
			while arr[i] <= mini:
				i += 1
			j = len(arr) - 1
			while arr[j] >= maxi:
				j -= 1
			ans.append(i)
			ans.append(j)
			return ans


from typing import List

class Solution:

	def printUnsorted(self, arr: List[int], n: int) -> List[int]:
		if n != len(arr):
			raise ValueError('wrong n!')
		if n == 0:
			raise ValueError('empty array')
		if n == 1:
			return [0, 0]
		left = 0
		while left < n - 1 and arr[left] <= arr[left + 1]:
			left += 1
		if left == n - 1:
			return [0, 0]
		right = n - 1
		while right > 0 and arr[right - 1] <= arr[right]:
			right -= 1
		minim = float('+inf')
		maxim = float('-inf')
		for i in range(left, 1 + right):
			minim = min(minim, arr[i])
			maxim = max(maxim, arr[i])
		new_left = left
		for i in range(left):
			if arr[i] > minim:
				new_left = i
				break
		new_right = right
		for i in range(n - 1, right, -1):
			if arr[i] < maxim:
				new_right = i
				break
		return [new_left, new_right]


class Solution:

	def printUnsorted(self, arr, n):
		new = arr[:]
		new.sort()
		s = 0
		r = 0
		for i in range(0, len(arr)):
			if arr[i] != new[i]:
				s = i
				break
		for i in range(len(arr) - 1, -1, -1):
			if arr[i] != new[i]:
				r = i
				break
		return (s, r)


class Solution:

	def printUnsorted(self, arr, n):
		i = 0
		j = 1
		min = max = -1
		ans = [0, 0]
		while j < n:
			if arr[i] > arr[j]:
				if min == -1:
					min = arr[j]
				elif min > arr[j]:
					min = arr[j]
			i += 1
			j += 1
		if min == -1:
			return [0, 0]
		else:
			for i in range(n):
				if arr[i] > min:
					ans[0] = i
					break
		i = n - 1
		j = i - 1
		while j >= 0:
			if arr[i] < arr[j]:
				if max == -1:
					max = arr[j]
				elif max < arr[j]:
					max = arr[j]
			j -= 1
			i -= 1
		for i in range(n - 1, -1, -1):
			if arr[i] < max:
				ans[1] = i
				break
		return ans


import sys

class Solution:

	def printUnsorted(self, arr, n):
		(low, high) = (0, n - 1)
		while low < n - 1 and arr[low] <= arr[low + 1]:
			low += 1
		if low == n - 1:
			return (0, 0)
		while high > 0 and arr[high] >= arr[high - 1]:
			high -= 1
		maxx = -sys.maxsize
		minn = sys.maxsize
		for k in range(low, high + 1):
			maxx = max(maxx, arr[k])
			minn = min(minn, arr[k])
		while low > 0 and arr[low - 1] > minn:
			low -= 1
		while high < n - 1 and arr[high + 1] < maxx:
			high += 1
		return (low, high)


class Solution:

	def printUnsorted(self, arr, n):
		n = len(arr)
		s = 0
		e = n - 1
		while s < n - 1 and arr[s] <= arr[s + 1]:
			s += 1
		if s == n - 1:
			return (0, 0)
		while e > 0 and arr[e] >= arr[e - 1]:
			e -= 1
		min_val = arr[s]
		max_val = arr[s]
		for i in range(s + 1, e + 1):
			min_val = min(min_val, arr[i])
			max_val = max(max_val, arr[i])
		for i in range(0, s):
			if arr[i] > min_val:
				s = i
				break
		for i in range(n - 1, e, -1):
			if arr[i] < max_val:
				e = i
				break
		return (s, e)


class Solution:

	def printUnsorted(self, arr, n):
		arr_1 = sorted(arr)
		if n == 1:
			return [0, 0]
		for i in range(n):
			if arr[i] != arr_1[i]:
				lb = i
				break
		for i in range(n - 1, 0, -1):
			if arr[i] != arr_1[i]:
				ub = i
				break
		return [lb, ub]


class Solution:

	def printUnsorted(self, arr, n):
		i = 0
		while i < n - 1 and arr[i + 1] >= arr[i]:
			i += 1
		if i == n - 1:
			return [0, 0]
		left_idx = i
		i = n - 1
		while i > 1 and arr[i] >= arr[i - 1]:
			i -= 1
		right_idx = i
		min_num = arr[left_idx]
		max_num = arr[left_idx]
		for i in range(left_idx + 1, right_idx + 1):
			min_num = min(min_num, arr[i])
			max_num = max(max_num, arr[i])
		start = left_idx
		end = right_idx
		for j in range(left_idx - 1, -1, -1):
			if arr[j] > min_num:
				start = j
		for j in range(right_idx + 1, n):
			if arr[j] < max_num:
				end = j
		return [start, end]


class Solution:

	def printUnsorted(self, arr, n):
		a = arr.copy()
		a.sort()
		first = 0
		for i in range(n):
			if arr[i] != a[i]:
				first = i
				break
			else:
				continue
		second = 0
		for i in range(n - 1, -1, -1):
			if arr[i] != a[i]:
				second = i
				break
			else:
				continue
		return (first, second)


class Solution:

	def printUnsorted(self, arr, n):
		Min = 10 ** 8
		Max = -1
		if n == 1:
			return [0, 0]
		for i in range(n):
			if i == 0:
				if arr[i] > arr[i + 1]:
					Min = min(Min, arr[i])
					Max = max(Max, arr[i])
			elif i == n - 1:
				if arr[i - 1] > arr[i]:
					Min = min(Min, arr[i])
					Max = max(Max, arr[i])
			elif arr[i] > arr[i + 1] or arr[i - 1] > arr[i]:
				Min = min(Min, arr[i])
				Max = max(Max, arr[i])
		if Min == 10 ** 8 and Max == -1:
			return [0, 0]
		(i, j) = (0, n - 1)
		while arr[i] <= Min:
			i = i + 1
		while arr[j] >= Max:
			j = j - 1
		return [i, j]


import sys

class Solution:

	def printUnsorted(self, arr, n):
		(startIdx, endIdx) = (0, 0)
		maxElem = -sys.maxsize
		minElem = sys.maxsize
		for startIdx in range(len(arr) - 1):
			if arr[startIdx + 1] < arr[startIdx]:
				break
		for endIdx in range(len(arr) - 1, startIdx, -1):
			if arr[endIdx] < arr[endIdx - 1]:
				break
		if startIdx == endIdx - 1:
			maxElem = arr[startIdx]
			minElem = arr[endIdx]
		elif startIdx == endIdx - 2:
			maxElem = arr[startIdx]
			minElem = arr[startIdx + 1]
		else:
			for i in range(startIdx + 1, endIdx):
				if arr[i] < minElem:
					minElem = arr[i]
				if arr[i] > maxElem:
					maxElem = arr[i]
		for startIdx in range(startIdx, -1, -1):
			if startIdx == 0:
				break
			if arr[startIdx - 1] <= minElem:
				break
		for endIdx in range(endIdx, len(arr)):
			if endIdx == len(arr) - 1:
				break
			if arr[endIdx + 1] >= maxElem:
				break
		return (startIdx, endIdx)


class Solution:

	def printUnsorted(self, arr, n):
		start = -1
		end = -1
		for i in range(n - 1):
			if arr[i] > arr[i + 1]:
				start = i
				break
		for i in range(n - 1, 0, -1):
			if arr[i - 1] > arr[i]:
				end = i
				break
		if start == -1:
			return (0, 0)
		mn = arr[start]
		mx = arr[start]
		for i in range(start, end + 1):
			if arr[i] < mn:
				mn = arr[i]
			elif arr[i] > mx:
				mx = arr[i]
		for (i, ele) in enumerate(arr):
			if mn < ele:
				start = i
				break
		for i in range(n - 1, 0, -1):
			if arr[i] < mx:
				end = i
				break
		return (start, end)


class Solution:

	def printUnsorted(self, arr, n):
		c = -1
		b = -1
		v = sorted(arr)
		if v == arr:
			return [0, 0]
		for i in range(n):
			if v[i] != arr[i]:
				c = i
				break
		for i in range(n - 1, -1, -1):
			if v[i] != arr[i]:
				b = i
				break
		if c == -1 or b == -1:
			return [0]
		else:
			return [c, b]


class Solution:

	def printUnsorted(self, arr, n):
		(s, e) = [0, 0]
		for i in range(n - 1):
			if arr[i] > arr[i + 1]:
				s = i
				break
		for i in range(n - 1, 0, -1):
			if arr[i] < arr[i - 1]:
				e = i
				break
		(Min, Max) = (int(1000000000.0), -int(1000000000.0))
		for i in range(s, e + 1):
			Min = min(Min, arr[i])
			Max = max(Max, arr[i])
		for i in range(s + 1):
			if arr[i] > Min:
				s = i
				break
		for i in range(n - 1, e - 1, -1):
			if arr[i] < Max:
				e = i
				break
		return [s, e]


class Solution:

	def printUnsorted(self, arr, n):
		(s, e) = [0, 0]
		for i in range(n - 1):
			if arr[i] > arr[i + 1]:
				s = i
				break
		for i in range(n - 1, 0, -1):
			if arr[i] < arr[i - 1]:
				e = i
				break
		(Min, Max) = (2 ** 63, -2 ** 63)
		for i in range(s, e + 1):
			Min = min(Min, arr[i])
			Max = max(Max, arr[i])
		for i in range(s + 1):
			if arr[i] > Min:
				s = i
				break
		for i in range(n - 1, e - 1, -1):
			if arr[i] < Max:
				e = i
				break
		return [s, e]


class Solution:

	def printUnsorted(self, arr, n):
		arr2 = sorted(arr)
		result = [0, 0]
		for i in range(n):
			if arr[i] != arr2[i]:
				result[0] = i
				break
		for i in range(n):
			if arr[-i - 1] != arr2[-i - 1]:
				result[1] = n - 1 - i
				break
		return result


class Solution:

	def printUnsorted(self, arr, n):
		if n == 1:
			return (0, 0)
		l = n
		r = 0
		s = sorted(arr)
		for i in range(n):
			if s[i] != arr[i]:
				l = min(l, i)
				r = max(r, i)
		return (l, r)


class Solution:

	def printUnsorted(self, arr, n):
		arr_sorted = sorted(arr)
		diff_arr = [arr[i] - arr_sorted[i] for i in range(len(arr))]
		i1 = 0
		i2 = 0
		for i in range(len(diff_arr)):
			if diff_arr[i] != 0:
				i1 = i
				break
		for i in range(len(diff_arr) - 1, -1, -1):
			if diff_arr[i] != 0:
				i2 = i
				break
		return (i1, i2)


class Solution:

	def printUnsorted(self, arr, n):
		if len(arr) == 1:
			return [0, 0]
		indices = []
		temp = sorted(arr)
		for index in range(n):
			if arr[index] ^ temp[index] != 0:
				indices.append(index)
		return [min(indices), max(indices)]


import sys

class Solution:

	def out_of_order(self, arr, i):
		x = arr[i]
		if i == 0:
			return x > arr[1]
		if i == len(arr) - 1:
			return x < arr[i - 1]
		return x < arr[i - 1] or x > arr[i + 1]

	def printUnsorted(self, arr, n):
		if n <= 1:
			return [0, 0]
		smallest = sys.maxsize
		largest = -sys.maxsize - 1
		for i in range(n):
			if self.out_of_order(arr, i):
				smallest = min(smallest, arr[i])
				largest = max(largest, arr[i])
		if smallest == sys.maxsize:
			return [-1, -1]
		left = 0
		while smallest >= arr[left]:
			left += 1
		right = len(arr) - 1
		while largest <= arr[right]:
			right -= 1
		return [left, right]


class Solution:

	def printUnsorted(self, arr, n):
		s = e = -1
		for i in range(n - 1):
			if arr[i] > arr[i + 1]:
				s = i
				break
		for j in range(n - 1, 0, -1):
			if arr[j] < arr[j - 1]:
				e = j
				break
		if s == -1 or e == -1:
			return [0, 0]
		(max_num, min_num) = (s, s)
		for i in range(s, e + 1):
			if arr[i] < arr[min_num]:
				min_num = i
			if arr[i] > arr[max_num]:
				max_num = i
		for i in range(0, s + 1):
			if arr[i] > arr[min_num]:
				s = i
				break
		for j in range(n - 1, e, -1):
			if arr[j] < arr[max_num]:
				e = j
				break
		return [s, e]


class Solution:

	def printUnsorted(self, arr, n):
		s = sorted(arr)
		ans = []
		for k in range(n):
			if arr[k] != s[k]:
				if ans == []:
					ans.append(k)
					ans.append(k)
				else:
					ans[1] = k
		if ans == []:
			return [0, 0]
		return ans


class Solution:

	def printUnsorted(self, arr, n):
		e = n - 1
		if n == 1:
			return (0, 0)
		for s in range(0, n - 1):
			if arr[s] > arr[s + 1]:
				break
		if s == n - 1:
			return (0, 0)
		e = n - 1
		while e > 0:
			if arr[e] < arr[e - 1]:
				break
			e -= 1
		max = arr[s]
		min = arr[s]
		for i in range(s + 1, e + 1):
			if arr[i] > max:
				max = arr[i]
			if arr[i] < min:
				min = arr[i]
		for i in range(s):
			if arr[i] > min:
				s = i
				break
		i = n - 1
		while i >= e + 1:
			if arr[i] < max:
				e = i
				break
			i -= 1
		return (s, e)


class Solution:

	def printUnsorted(self, arr, n):

		def asc(arr, n):
			i = 0
			while i < n - 1 and arr[i + 1] >= arr[i]:
				i += 1
			left = i
			i = n - 1
			while i > 0 and arr[i - 1] <= arr[i]:
				i -= 1
			right = i
			min_num = min(arr[left:right + 1])
			max_num = max(arr[left:right + 1])
			i = 0
			while i < n - 1 and arr[i] <= min_num:
				i += 1
			j = n - 1
			while j > 0 and arr[j] >= max_num:
				j -= 1
			return (i, j)
		return asc(arr, n)


class Solution:

	def printUnsorted(self, arr, n):
		result = []
		for i in range(n):
			result.append(arr[i])
		result.sort()
		start = -1
		for i in range(n):
			if result[i] != arr[i]:
				start = i
				break
		end = -1
		for i in range(n - 1, -1, -1):
			if result[i] != arr[i]:
				end = i
				break
		if start != -1 and end != -1:
			return [start, end]
		else:
			return [0, 0]


import math

class Solution:

	def printUnsorted(self, arr, n):
		start = -1
		end = -1
		max_so_far = -math.inf
		for i in range(len(arr)):
			if arr[i] < max_so_far:
				if start == -1:
					start = i - 1
				while start - 1 >= 0 and arr[start - 1] > arr[i]:
					start -= 1
				end = i
			else:
				max_so_far = arr[i]
		if end == -1:
			return [0, 0]
		return [start, end]


class Solution:

	def printUnsorted(self, arr, n):
		s = 0
		e = 0
		for i in range(n - 1):
			if arr[i] > arr[i + 1]:
				s = i
				break
		for i in range(n - 1, 1, -1):
			if arr[i] < arr[i - 1]:
				e = i
				break
		mn = s
		mx = s
		for i in range(s, e + 1):
			if arr[i] > arr[mx]:
				mx = i
			if arr[i] < arr[mn]:
				mn = i
		for i in range(s):
			if arr[i] > arr[mn]:
				s = i
				break
		for i in range(n - 1, e, -1):
			if arr[i] < arr[mx]:
				e = i
				break
		return [s, e]


class Solution:

	def printUnsorted(self, arr, n):
		l = arr.copy()
		l.sort()
		if l == arr:
			return [0, 0]
		le = -1
		r = -1
		for i in range(n):
			if arr[i] != l[i]:
				le = i
				break
		for j in range(n - 1, i, -1):
			if arr[j] != l[j]:
				r = j
				break
		return [le, r]


class Solution:

	def printUnsorted(self, arr, n):
		e = n - 1
		for s in range(0, n - 1):
			if arr[s] > arr[s + 1]:
				break
		if n == 1:
			return [0, 0]
		if s == n - 1:
			return [0, 0]
		while e > 0:
			if arr[e] < arr[e - 1]:
				break
			e -= 1
		maxx = arr[s]
		minn = arr[s]
		for i in range(s + 1, e + 1):
			if arr[i] > maxx:
				maxx = arr[i]
			if arr[i] < minn:
				minn = arr[i]
		for i in range(s):
			if arr[i] > minn:
				s = i
				break
		i = n - 1
		while i >= e + 1:
			if arr[i] < maxx:
				e = i
				break
			i -= 1
		return [s, e]


class Solution:

	def printUnsorted(self, arr, n):
		first = 0
		last = 0
		l = arr.copy()
		l.sort()
		for i in range(len(l)):
			if l[i] != arr[i]:
				first = i
		for i in range(n - 1, -1, -1):
			if l[i] != arr[i]:
				last = i
		return (last, first)


class Solution:

	def printUnsorted(self, arr, n):
		(l, r) = (0, 0)
		num = []
		for a in arr:
			num.append(a)
		num.sort()
		for i in range(n):
			if num[i] != arr[i]:
				l = i
				break
		for i in range(n - 1, -1, -1):
			if num[i] != arr[i]:
				r = i
				break
		return [l, r]


class Solution:

	def printUnsorted(self, arr, n):
		min_arr = [0] * n
		min_arr[n - 1] = arr[n - 1]
		for i in range(n - 2, -1, -1):
			min_arr[i] = min(min_arr[i + 1], arr[i])
		max_arr = [0] * n
		max_arr[0] = arr[0]
		for i in range(1, n):
			max_arr[i] = max(max_arr[i - 1], arr[i])
		s = 0
		e = n - 1
		while s < n and min_arr[s] == max_arr[s]:
			s += 1
		while e >= 0 and min_arr[e] == max_arr[e]:
			e -= 1
		if s == n:
			return [0, 0]
		return [s, e]


class Solution:

	def printUnsorted(self, arr, n):
		a = []
		a[:] = arr[:]
		a.sort()
		index1 = 0
		index2 = 0
		for i in range(n):
			if a[i] != arr[i]:
				index1 = i
		for i in range(n - 1, -1, -1):
			if a[i] != arr[i]:
				index2 = i
		return (index2, index1)


class Solution:

	def printUnsorted(self, arr, n):
		ans = [1000000, 0]
		a1 = sorted(arr)
		if n == 1:
			return [0, 0]
		else:
			for i in range(n):
				if arr[i] != a1[i]:
					ans[0] = min(ans[0], i)
					ans[1] = max(ans[1], i)
			return ans


class Solution:

	def printUnsorted(self, arr, n):
		k = sorted(list(enumerate(arr)), key=lambda x: x[1])
		start = 0
		for i in range(len(arr)):
			if arr[i] == k[i][1]:
				continue
			else:
				start = i
				break
		end = 0
		for j in range(len(arr) - 1, -1, -1):
			if arr[j] == k[j][1]:
				continue
			else:
				end = j
				break
		if start or end != 0:
			return (start, end)
		else:
			return (0, 0)


class Solution:

	def printUnsorted(self, arr, n):
		start = 0
		end = n - 1
		for i in range(n - 1):
			if arr[i] <= arr[i + 1]:
				start = i + 1
			else:
				break
		for i in range(n - 1, start, -1):
			if arr[i] >= arr[i - 1]:
				end = i - 1
			else:
				break
		mi = arr[start]
		mx = arr[end]
		for i in range(start, end + 1):
			if arr[i] < mi:
				mi = arr[i]
			elif arr[i] > mx:
				mx = arr[i]
		for i in range(start, -1, -1):
			if arr[i] > mi:
				start = i
			else:
				break
		for i in range(end, n):
			if arr[i] < mx:
				end = i
			else:
				break
		return (start, end)


class Solution:

	def printUnsorted(self, arr, n):
		s = sorted(arr)
		temp = []
		i = 0
		while i < len(arr):
			if arr[i] != s[i]:
				temp.append(i)
			i += 1
		if temp:
			return [min(temp), max(temp)]
		return [0, 0]
		s = sorted(arr)
		temp = []
		i = 0
		while i < len(arr):
			if arr[i] != s[i]:
				temp.append(i)
			i += 1
		if temp:
			return [min(temp), max(temp)]


class Solution:

	def printUnsorted(self, arr, n):
		a = b = 0
		l = arr.copy()
		l.sort()
		for i in range(n):
			if l[i] != arr[i]:
				a = i
				break
		for i in range(n - 1, -1, -1):
			if l[i] != arr[i]:
				b = i
				break
		return [a, b]


class Solution:

	def printUnsorted(self, arr, n):
		lst = []
		for j in range(0, len(arr)):
			lst.append(arr[j])
		arr.sort()
		b = []
		for i in range(0, len(arr)):
			if arr[i] != lst[i]:
				b.append(i)
		try:
			return [min(b), max(b)]
		except:
			return [0, 0]


class Solution:

	def printUnsorted(self, arr, n):
		import sys
		s = 0
		e = 0
		suffix_min = arr[n - 1]
		k = n - 2
		while k > -1:
			suffix_min = min(suffix_min, arr[k])
			if suffix_min != arr[k]:
				s = k
			k -= 1
		prefix_max = arr[0]
		k = 1
		while k < n:
			prefix_max = max(prefix_max, arr[k])
			if prefix_max != arr[k]:
				e = k
			k += 1
		return (s, e)


class Solution:

	def printUnsorted(self, arr, n):
		b = arr[:]
		b.sort()
		i = 0
		while i < n and b[i] == arr[i]:
			i += 1
		j = n - 1
		while j >= 0 and b[j] == arr[j]:
			j -= 1
		if i > j:
			return [0, 0]
		return [i, j]


class Solution:

	def printUnsorted(self, arr, n):
		res = []
		for (i, n) in enumerate(arr):
			res.append((n, i))
		res.sort()
		data = []
		for (j, (n, i)) in enumerate(res):
			if i == j:
				pass
			else:
				data.append(i)
		if len(data) == 0:
			return [0, 0]
		return [min(data), max(data)]


class Solution:

	def printUnsorted(self, arr, n):
		if len(arr) == 1:
			return [0, 0]
		else:
			m1 = arr[0]
			k = 0
			flag = 0
			for i in range(1, n):
				if arr[i] > m1 and flag == 0:
					m1 = arr[i]
				if arr[i] < m1:
					m1 = arr[i]
					flag = 1
			if m1 < arr[0]:
				k = -1
			else:
				for i in range(n):
					if m1 >= arr[i]:
						k = i
					if m1 < arr[i]:
						break
			flag1 = 0
			mx1 = arr[n - 1]
			k1 = 0
			for i in range(n - 1, -1, -1):
				if arr[i] < mx1 and flag1 == 0:
					mx1 = arr[i]
				if arr[i] > mx1:
					mx1 = arr[i]
					flag1 = 1
			if mx1 > arr[n - 1]:
				k1 = n
			else:
				for i in range(n - 1, -1, -1):
					if mx1 <= arr[i]:
						k1 = i
					if mx1 > arr[i]:
						break
			return [k + 1, k1 - 1]


class Solution:

	def printUnsorted(self, arr, n):
		ans = [0] * 2
		start = n - 1
		for start in range(0, n - 1):
			if arr[start] > arr[start + 1]:
				break
		if start == n - 1:
			return ans
		for end in range(n - 1, 0, -1):
			if arr[end] < arr[end - 1]:
				break
		max_val = max(arr[start:end + 1])
		min_val = min(arr[start:end + 1])
		for i in range(start):
			if arr[i] > min_val:
				start = i
				break
		for j in range(n - 1, end - 1, -1):
			if arr[j] < max_val:
				end = j
				break
		ans[0] = start
		ans[1] = end
		return ans


class Solution:

	def printUnsorted(self, arr, n):
		(l, r) = (0, n - 1)
		while l < n - 1 and arr[l] <= arr[l + 1]:
			l += 1
		while r > 0 and arr[r] >= arr[r - 1]:
			r -= 1
		(maxi, mini) = (-float('inf'), float('inf'))
		for i in range(l, r + 1):
			maxi = max(maxi, arr[i])
			mini = min(mini, arr[i])
		while l > 0 and arr[l - 1] > mini:
			l -= 1
		while r < n - 1 and arr[r + 1] < maxi:
			r += 1
		return [l, r]


class Solution:

	def printUnsorted(self, arr, n):
		a = sorted(arr)
		ans = 0
		ans1 = 0
		for i in range(n):
			if a[i] != arr[i]:
				ans = i
				break
		for i in range(n - 1, -1, -1):
			if a[i] != arr[i]:
				ans1 = i
				break
		return (ans, ans1)


class Solution:

	def printUnsorted(self, arr, n):
		x = sorted(arr)
		if arr == x:
			return [0, 0]
		l = []
		for i in range(n):
			if arr[i] != x[i]:
				l.append(i)
		return [l[0], l[-1]]


class Solution:

	def printUnsorted(self, arr, n):
		pre_max = arr[0]
		suf_min = arr[n - 1]
		s = 0
		e = 0
		for i in range(1, n):
			pre_max = max(pre_max, arr[i])
			if pre_max != arr[i]:
				e = i
		for i in reversed(range(n - 1)):
			suf_min = min(suf_min, arr[i])
			if suf_min != arr[i]:
				s = i
		return [s, e]


class Solution:

	def printUnsorted(self, arr, n):
		end = n - 1
		start = 0
		for start in range(0, n - 1):
			if arr[start] > arr[start + 1]:
				break
		while end > 0:
			if arr[end] < arr[end - 1]:
				break
			end -= 1
		maxi = arr[start]
		mini = arr[start]
		for i in range(start + 1, end + 1):
			if arr[i] > maxi:
				maxi = arr[i]
			if arr[i] < mini:
				mini = arr[i]
		for i in range(start):
			if arr[i] > mini:
				start = i
				break
		i = n - 1
		while i >= end + 1:
			if arr[i] < maxi:
				end = i
				break
			i -= 1
		return [start, end]
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.printUnsorted(arr, n)
		print(str(ans[0]) + ' ' + str(ans[1]))
		tc -= 1


import sys

class Solution:

	def printUnsorted(self, arr, n):
		maximum = -sys.maxsize
		minimum = sys.maxsize
		max_index = min_index = -1
		for i in range(n):
			if i == 0:
				maximum = arr[i]
			elif arr[i] >= maximum:
				maximum = arr[i]
			else:
				max_index = i
		if max_index == -1:
			return [0, 0]
		for i in range(n - 1, -1, -1):
			if i == n - 1:
				minimum = arr[i]
			elif arr[i] <= minimum:
				minimum = arr[i]
			else:
				min_index = i
		return (min_index, max_index)
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.printUnsorted(arr, n)
		print(str(ans[0]) + ' ' + str(ans[1]))
		tc -= 1


class Solution:

	def printUnsorted(self, arr, n):
		l = r = 0
		num = arr.copy()
		num.sort()
		for i in range(n):
			if num[i] != arr[i]:
				l = i
				break
		for i in range(n - 1, l, -1):
			if arr[i] != num[i]:
				r = i
				break
		return [l, r]
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.printUnsorted(arr, n)
		print(str(ans[0]) + ' ' + str(ans[1]))
		tc -= 1


class Solution:

	def printUnsorted(self, arr, n):
		e = n - 1
		s = 0
		for s in range(n - 1):
			if arr[s] > arr[s + 1]:
				break
		if s == n - 1:
			return [0, 0]
		e = n - 1
		while e > 0:
			if arr[e] < arr[e - 1]:
				break
			e -= 1
		max = arr[s]
		min = arr[s]
		for i in range(s + 1, e + 1):
			if arr[i] > max:
				max = arr[i]
			if arr[i] < min:
				min = arr[i]
		for i in range(s):
			if arr[i] > min:
				s = i
				break
		i = n - 1
		while i >= e + 1:
			if arr[i] < max:
				e = i
				break
			i -= 1
		return [s, e]
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.printUnsorted(arr, n)
		print(str(ans[0]) + ' ' + str(ans[1]))
		tc -= 1


class Solution:

	def printUnsorted(self, arr, n):
		if len(arr) == 1:
			return [0, 0]
		elif len(arr) == 2:
			if arr == list(sorted(arr)):
				return [0, 0]
			else:
				return [0, 1]
		else:
			ans = [0, 0]
			for i in range(n):
				if arr[i] > arr[i + 1]:
					ans[0] = i
					break
			for i in range(n - 1, -1, -1):
				if arr[i] < arr[i - 1]:
					ans[1] = i
					break
			maxi = max(arr[ans[0]:ans[1] + 1])
			mini = min(arr[ans[0]:ans[1] + 1])
			while ans[0] >= 1 and arr[ans[0] - 1] > mini:
				ans[0] -= 1
			while ans[1] < n - 1 and arr[ans[1] + 1] < maxi:
				ans[1] += 1
			return ans
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.printUnsorted(arr, n)
		print(str(ans[0]) + ' ' + str(ans[1]))
		tc -= 1


class Solution:

	def printUnsorted(self, arr, n):
		(Min, Max) = (float('inf'), float('-inf'))
		if n == 1:
			return (0, 0)
		for i in range(n):
			if i == 0:
				if arr[i] > arr[i + 1]:
					Min = min(Min, arr[i])
					Max = max(Max, arr[i])
			elif i == n - 1:
				if arr[i] < arr[i - 1]:
					Min = min(Min, arr[i])
					Max = max(Max, arr[i])
			elif arr[i] > arr[i + 1] or arr[i] < arr[i - 1]:
				Min = min(Min, arr[i])
				Max = max(Max, arr[i])
		if Min == float('inf') or Max == float('-inf'):
			return (0, 0)
		(l, r) = (0, n - 1)
		while l < n and arr[l] <= Min:
			l += 1
		while r >= 0 and arr[r] >= Max:
			r -= 1
		return (l, r)
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.printUnsorted(arr, n)
		print(str(ans[0]) + ' ' + str(ans[1]))
		tc -= 1


class Solution:

	def printUnsorted(self, arr, n):
		l = []
		for i in range(n):
			l.append(arr[i])
		l.sort()
		k = []
		for i in range(n):
			if arr[i] != l[i]:
				k.append(i)
		if len(k) > 0:
			return (k[0], k[len(k) - 1])
		else:
			return (0, 0)
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.printUnsorted(arr, n)
		print(str(ans[0]) + ' ' + str(ans[1]))
		tc -= 1


class Solution:

	def printUnsorted(self, arr, n):
		max_ele = arr[0]
		(first_ind, last_ind) = (0, 0)
		for i in range(1, n):
			if arr[i] < max_ele:
				last_ind = i
			max_ele = max(max_ele, arr[i])
		min_ele = arr[n - 1]
		for i in reversed(range(n - 1)):
			if arr[i] > min_ele:
				first_ind = i
			min_ele = min(min_ele, arr[i])
		return [first_ind, last_ind]
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.printUnsorted(arr, n)
		print(str(ans[0]) + ' ' + str(ans[1]))
		tc -= 1


class Solution:

	def printUnsorted(self, nums, n):
		l = 0
		r = len(nums) - 1
		while l < n - 1 and nums[l + 1] >= nums[l]:
			l += 1
		if l == n - 1:
			return [l, r]
		while r >= 0 and nums[r] >= nums[r - 1]:
			r -= 1
		if r == 0:
			return [l, r]
		maxm = max(nums[l:r + 1])
		minm = min(nums[l:r + 1])
		l = 0
		r = n - 1
		while l < n and nums[l] <= minm:
			l += 1
		while r > 0 and nums[r] >= maxm:
			r -= 1
		return [l, r]
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.printUnsorted(arr, n)
		print(str(ans[0]) + ' ' + str(ans[1]))
		tc -= 1


class Solution:

	def printUnsorted(self, arr, n):
		a = arr.copy()
		a.sort()
		x = 0
		y = 0
		for i in range(n):
			if a[i] != arr[i]:
				x = i
				break
		for i in range(n):
			if a[i] != arr[i]:
				y = i
		return (x, y)
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.printUnsorted(arr, n)
		print(str(ans[0]) + ' ' + str(ans[1]))
		tc -= 1


class Solution:

	def printUnsorted(self, arr, n):
		if n == 1:
			return (0, 0)
		s1 = s2 = -1
		for i in range(n - 1):
			if arr[i] > arr[i + 1]:
				s1 = i
				break
		for i in range(n - 1, 0, -1):
			if arr[i - 1] > arr[i]:
				s2 = i
				break
		mi = 1000000
		ma = -1000000
		for i in range(s1, s2 + 1):
			ma = max(ma, arr[i])
			mi = min(mi, arr[i])
		if mi < arr[s1]:
			while s1 >= 0 and arr[s1] > mi:
				s1 -= 1
		if ma > arr[s2]:
			while s2 < n and arr[s2] < ma:
				s2 += 1
		return (s1 + 1, s2 - 1)
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.printUnsorted(arr, n)
		print(str(ans[0]) + ' ' + str(ans[1]))
		tc -= 1


import sys

class Solution:

	def printUnsorted(self, arr, n):
		mn = sys.maxsize
		mx = -sys.maxsize - 1
		for i in range(1, n):
			if arr[i] < arr[i - 1]:
				mn = min(mn, arr[i])
		for i in range(n - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				mx = max(mx, arr[i])
		i = 0
		while i < n:
			if arr[i] > mn:
				break
			i += 1
		j = n - 1
		while j >= 0:
			if arr[j] < mx:
				break
			j -= 1
		if j - i >= 0:
			return [i, j]
		else:
			return [0, 0]