Given an array of n distinct elements. Find the length of shortest unordered (neither increasing nor decreasing) sub array in given array.
 
Example 1:
Input:
n = 5
a[] = {7, 9, 10, 8, 11}
Output:
3
Explanation:
Shortest unsorted subarray is 9, 10, 8
which is of 3 elements.
 
Example 2:
Input:
n = 4
a[] = {1, 2, 3, 5}
Output:
0
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function shortestUnorderedSubarray() which takes the array a[] and its size n as inputs and returns the length of shortest unordered subarray.
 
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= n <= 10^{5}
1 <= a[i] <= 10^{5}

Difficulty: EASY
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3

class Solution:
    def shortestUnorderedSubarray(self, a, n):
        #Code here
    
    
    

Solutions:
class Solution:

	def shortestUnorderedSubarray(self, a, n):
		a = [int(x) for x in a]
		for index in range(n - 2):
			if a[index] < a[index + 1] > a[index + 2] or a[index] > a[index + 1] < a[index + 2]:
				return 3
		return 0


class Solution:

	def shortestUnorderedSubarray(self, a, n):
		a = list(map(int, a))
		for i in range(1, n - 1):
			if a[i - 1] < a[i] and a[i] > a[i + 1]:
				return 3
			elif a[i - 1] > a[i] and a[i] < a[i + 1]:
				return 3
		return 0


class Solution:

	def shortestUnorderedSubarray(self, a, n):
		if n < 3:
			return 0
			s = ''
		for i in range(1, n - 1):
			if a[i - 1] < a[i] > a[i + 1]:
				s = a[i - 1] + a[i] + a[i + 1]
				print(s)
				return 3
			elif a[i - 1] > a[i] < a[i + 1]:
				s = a[i - 1] + a[i] + a[i + 1]
				print(s)
				return 3
		return 0

class Solution:

	def shortestUnorderedSubarray(self, a, n):
		a = list(map(int, a))
		if n < 3:
			return 0
		else:
			for i in range(n - 2):
				if a[i] > a[i + 1] and a[i + 1] < a[i + 2]:
					return 3
				if a[i] < a[i + 1] and a[i + 1] > a[i + 2]:
					return 3
		return 0


class Solution:

	def shortestUnorderedSubarray(self, a, n):
		a1 = [int(j) for j in a]
		r = 0
		cc = 0
		for j in range(1, n - 1):
			if a1[j] - a1[j - 1] < 0:
				if a1[j + 1] - a1[j] > 0:
					return 3
			elif a1[j + 1] - a1[j] < 0:
				return 3
		if r == 0:
			return 0
		else:
			return r


class Solution:

	def shortestUnorderedSubarray(self, a, n):
		a = [int(x) for x in a]
		if self.inc(a, n) or self.dec(a, n):
			return 0
		return 3

	def inc(self, a, n):
		for i in range(n - 1):
			if a[i] > a[i + 1]:
				return False
		return True

	def dec(self, a, n):
		for i in range(n - 1):
			if a[i] < a[i + 1]:
				return False
		return True


class Solution:

	def shortestUnorderedSubarray(self, a, n):
		if n == 1:
			return 0
		count = 0
		for i in range(n - 1):
			value1 = int(a[i])
			value2 = int(a[i + 1])
			if value1 > value2:
				count += 1
		if count == n - 1:
			return 0
		elif count == 0:
			return 0
		elif count != n - 1:
			return 3


class Solution:

	def shortestUnorderedSubarray(self, a, n):
		a = list(map(int, a))
		b = sorted(a)
		c = sorted(a, reverse=True)
		if n < 3:
			return 0
		elif n >= 3:
			if b == a or c == a:
				return 0
			else:
				return 3


class Solution:

	def shortestUnorderedSubarray(self, a, n):
		for i in range(n - 2):
			if int(a[i]) < int(a[i + 1]) and int(a[i + 1]) > int(a[i + 2]):
				return 3
			if int(a[i]) > int(a[i + 1]) and int(a[i + 1]) < int(a[i + 2]):
				return 3
		return 0


class Solution:

	def shortestUnorderedSubarray(self, arr, n):
		arr = list(map(int, arr))
		if n < 3:
			return 0
		flage = arr[0] < arr[1]
		if flage:
			for i in range(1, n):
				if arr[i - 1] > arr[i]:
					return 3
		else:
			for i in range(1, n):
				if arr[i] > arr[i - 1]:
					return 3
		return 0


class Solution:

	def isArray(self, arr):
		temp_inc = arr[:]
		temp_dec = arr[:]
		temp_inc.sort()
		if temp_inc == arr:
			return False
		temp_dec.sort(reverse=True)
		if temp_dec == arr:
			return False
		return True

	def shortestUnorderedSubarray(self, a, n):
		min_len = n
		a = list(map(int, a))
		if not self.isArray(a):
			return 0
		else:
			return 3
		for i in range(n):
			for j in range(i + 1, n + 1):
				arr = a[i:j]
				if (len(arr) > 1 and len(arr) < min_len) and self.isArray(arr):
					min_len = min(min_len, len(arr))
		return min_len


class Solution:

	def increase(self, a, n):
		for i in range(n - 1):
			if int(a[i]) >= int(a[i + 1]):
				return False
		return True

	def decrease(self, a, n):
		for i in range(n - 1):
			if int(a[i + 1]) > int(a[i]):
				return False
		return True

	def shortestUnorderedSubarray(self, a, n):
		if self.increase(a, n) or self.decrease(a, n):
			return 0
		else:
			return 3


class Solution:

	def increase(self, a, n):
		for i in range(n - 1):
			if int(a[i]) >= int(a[i + 1]):
				return False
		return True

	def decrease(self, a, n):
		for i in range(n - 1):
			if int(a[i + 1]) > int(a[i]):
				return False
		return True

	def shortestUnorderedSubarray(self, a, n):
		if self.increase(a, n) or self.decrease(a, n):
			return 0
		else:
			return 3

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [x for x in input().strip().split()]
		print(Solution().shortestUnorderedSubarray(a, n))
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def shortestUnorderedSubarray(self, arr, n):
		arr = [int(i) for i in arr]
		for i in range(n - 2):
			if not (arr[i] < arr[i + 1] and arr[i + 1] < arr[i + 2] or (arr[i] > arr[i + 1] and arr[i + 1] > arr[i + 2])):
				return 3
		return 0

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [x for x in input().strip().split()]
		print(Solution().shortestUnorderedSubarray(a, n))
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def shortestUnorderedSubarray(self, arr, n):
		aes = False
		if n == 1:
			return 0
		if int(arr[0]) < int(arr[1]):
			aes = True
		for i in range(1, n - 1):
			if aes:
				if int(arr[i]) > int(arr[i + 1]):
					return 3
			elif int(arr[i]) < int(arr[i + 1]):
				return 3
		return 0


class Solution:

	def shortestUnorderedSubarray(self, a, n):
		a = list(map(int, a))
		if n < 3:
			return 0
		res = float('inf')
		c = 1
		t = None
		prev = a[0]
		for i in a[1:]:
			if i == prev:
				c += 1
			elif t == None:
				if i > prev:
					c = 2
					t = 1
				else:
					c = 2
					t = -1
			elif i > prev:
				if t == 1:
					c = 2
				else:
					res = min(res, c + 1)
					c = 2
					t = 1
			elif t == 1:
				res = min(res, c + 1)
				c = 2
				t = -1
			else:
				c = 2
			prev = i
		return res if res != float('inf') else 0


class Solution:

	def increasing(self, a, n):
		for i in range(0, n - 1):
			if int(a[i]) > int(a[i + 1]):
				return False
		return True

	def decreasing(self, a, n):
		for i in range(0, n - 1):
			if int(a[i]) < int(a[i + 1]):
				return False
		return True

	def shortestUnorderedSubarray(self, a, n):
		if self.increasing(a, n) == True or self.decreasing(a, n) == True:
			return 0
		else:
			return 3


class Solution:

	def shortestUnorderedSubarray(self, a, n):
		(flag1, flag2) = (1, 1)
		for i in range(n - 1):
			if int(a[i]) < int(a[i + 1]):
				flag1 = 0
				break
		for i in range(n - 1):
			if int(a[i]) > int(a[i + 1]):
				flag2 = 0
				break
		if flag1 == 1 or flag2 == 1:
			return 0
		return 3