Given an array Arr[0 … N-1] containing N positive integers, a subarray Arr[i … j] is bitonic if there is a k with i <= k <= j such that A[i] <= Arr[i+1] <= ... <= Arr[k] >= Arr[k+1] >= ... A[j – 1] >= A[j]. Write a function that takes an array and array length as arguments and returns the length of the maximum length bitonic subarray.
For Example: In array {20, 4, 1, 2, 3, 4, 2, 10} the maximum length bitonic subarray is {1, 2, 3, 4, 2} which is of length 5.
Example 1:
Input:
N = 6
Arr[] = {12, 4, 78, 90, 45, 23}
Output: 5
Explanation: In the given array, 
bitonic subarray is 4 <= 78 <= 90
>= 45 >= 23.
Example 2:
Input:
N = 4
Arr[] = {10, 20, 30, 40}
Output: 4
Explanation: In the given array, 
bitonic subarray is 10 <= 20 <=
30 <= 40.
Your Task:
You don't need to read input or print anything. Your task is to complete the function bitonic() which takes the array of integers arr and n as parameters and returns an integer denoting the answer.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ Arr[i] ≤ 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3

class Solution:



	def bitonic(self,arr, n):

		# code here

Solutions:
class Solution:

	def bitonic(self, arr, n):
		if n == 0:
			return 0
		maxLen = 1
		start = 0
		nextStart = 0
		j = 0
		while j < n - 1:
			while j < n - 1 and arr[j] <= arr[j + 1]:
				j += 1
			while j < n - 1 and arr[j] >= arr[j + 1]:
				if j < n - 1 and arr[j] > arr[j + 1]:
					nextStart = j + 1
				j += 1
			maxLen = max(maxLen, j - (start - 1))
			start = nextStart
		return maxLen


class Solution:

	def bitonic(self, arr, n):
		dp = [1] * n
		for i in range(1, n):
			if arr[i] >= arr[i - 1]:
				dp[i] = dp[i - 1] + 1
		dp2 = [1] * n
		for i in range(n - 2, -1, -1):
			if arr[i] >= arr[i + 1]:
				dp2[i] = dp2[i + 1] + 1
		ans = 0
		for i in range(n):
			ans = max(ans, dp[i] + dp2[i] - 1)
		return ans


class Solution:

	def bitonic(self, a, n):
		ans = 0
		inc = 0
		dec = 0
		i = 0
		f = 0
		while i < n - 1:
			if f == 0:
				while i < n - 1 and a[i] <= a[i + 1]:
					inc += 1
					i += 1
				f = 1
			else:
				while i < n - 1 and a[i] >= a[i + 1]:
					if a[i] == a[i + 1]:
						cnt += 1
					else:
						cnt = 0
					dec += 1
					i += 1
				f = 0
				i -= cnt
				cnt = 0
			ans = max(ans, inc + dec)
			if f == 0:
				inc = 0
				dec = 0
		return ans + 1


class Solution:

	def bitonic(self, arr, n):
		inc = [None] * n
		dec = [None] * n
		inc[0] = 1
		dec[n - 1] = 1
		for i in range(1, n):
			if arr[i] >= arr[i - 1]:
				inc[i] = inc[i - 1] + 1
			else:
				inc[i] = 1
		for i in range(n - 2, -1, -1):
			if arr[i] >= arr[i + 1]:
				dec[i] = dec[i + 1] + 1
			else:
				dec[i] = 1
		ma = 0
		for i in range(n):
			ma = max(ma, inc[i] + dec[i] - 1)
		return ma


class Solution:

	def bitonic(self, arr, n):
		nums = arr
		n = len(nums)
		dp1 = [1 for i in range(n)]
		dp2 = [1 for i in range(n)]
		for i in range(1, n):
			if nums[i] >= nums[i - 1] and dp1[i] < dp1[i - 1] + 1:
				dp1[i] = dp1[i - 1] + 1
		for i in range(n - 2, -1, -1):
			if nums[i] >= nums[i + 1] and dp2[i] < dp2[i + 1] + 1:
				dp2[i] = dp2[i + 1] + 1
		maxi = 0
		for i in range(n):
			maxi = max(maxi, dp1[i] + dp2[i] - 1)
		return maxi


from bisect import bisect

class Solution:

	def bitonic(self, arr, n):
		maxi = 1
		i = 0
		count = 1
		while i < n - 1:
			count = 1
			j = 1
			while i - j >= 0 and arr[i] == arr[i - j]:
				count += 1
				j += 1
			while i < n - 1 and arr[i] <= arr[i + 1]:
				count += 1
				i += 1
			while i < n - 1 and arr[i] >= arr[i + 1]:
				count += 1
				i += 1
			maxi = max(maxi, count)
		return max(maxi, count)


class Solution:

	def bitonic(self, arr, n):
		increase = [1] * n
		prev = 0
		for i in range(1, n):
			if arr[i] >= arr[prev]:
				increase[i] = 1 + increase[prev]
			prev = i
		decrease = [1] * n
		prev = n - 1
		for i in range(n - 2, -1, -1):
			if arr[i] >= arr[prev]:
				decrease[i] = 1 + decrease[prev]
			prev = i
		ans = 0
		for i in range(0, n):
			ans = max(ans, increase[i] + decrease[i] - 1)
		return ans


class Solution:

	def bitonic(self, arr, n):
		front = [1] * n
		for i in range(1, n):
			if arr[i] >= arr[i - 1]:
				front[i] += front[i - 1]
			else:
				front[i] = 1
		back = [1] * n
		for i in range(n - 2, -1, -1):
			if arr[i] >= arr[i + 1]:
				back[i] += back[i + 1]
			else:
				back[i] = 1
		m = 1
		for i in range(n):
			m = max(front[i] + back[i] - 1, m)
		return m


class Solution:

	def bitonic(self, arr, n):
		lis = [1] * n
		lds = [1] * n
		for i in range(1, n):
			if arr[i] >= arr[i - 1]:
				lis[i] = lis[i - 1] + 1
		for j in range(n - 2, -1, -1):
			if arr[j] >= arr[j + 1]:
				lds[j] = lds[j + 1] + 1
		max1 = 0
		for i in range(n):
			max1 = max(max1, lis[i] + lds[i] - 1)
		return max1


class Solution:

	def bitonic(self, arr, n):
		left = [0] * n
		left[0] = 1
		for i in range(1, n):
			if arr[i] >= arr[i - 1]:
				left[i] = left[i - 1] + 1
			else:
				left[i] = 1
		right = [0] * n
		right[n - 1] = 1
		for i in range(n - 2, -1, -1):
			if arr[i] >= arr[i + 1]:
				right[i] = right[i + 1] + 1
			else:
				right[i] = 1
		max_len = 0
		for i in range(n):
			max_len = max(max_len, left[i] + (right[i] - 1))
		return max_len


class Solution:

	def bitonic(self, arr, n):
		start = 0
		next = 0
		maxx = 1
		i = 0
		while i < n - 1:
			while i < n - 1 and arr[i] <= arr[i + 1]:
				i += 1
			while i < n - 1 and arr[i] >= arr[i + 1]:
				if arr[i] > arr[i + 1]:
					next = i + 1
				i += 1
			maxx = max(maxx, i - start + 1)
			start = next
		return maxx


class Solution:

	def bitonic(self, arr, n):
		count = 0
		flag = 0
		ans = 0
		same = 0
		for i in range(1, n):
			if arr[i] >= arr[i - 1] and flag == 0:
				count += 1
				same = 0
			if arr[i] > arr[i - 1] and flag == 1:
				ans = max(count, ans)
				if same != 0:
					count = 1 + same
				else:
					count = 1
				flag = 0
				same = 0
			if arr[i] < arr[i - 1] and flag == 1:
				count += 1
				same = 0
			if arr[i] == arr[i - 1] and flag == 1:
				same += 1
				count += 1
			if arr[i] < arr[i - 1] and flag == 0:
				flag = 1
				count += 1
		ans = max(count, ans)
		return ans + 1


class Solution:

	def bitonic(self, arr, n):
		inc = [1]
		dec = [1]
		count_d = 1

		def increase(arr, n):
			inc = [1]
			count_i = 1
			for i in range(1, n):
				if arr[i - 1] <= arr[i]:
					count_i += 1
				else:
					count_i = 1
				inc.append(count_i)
			return inc
		inc = increase(arr, n)
		dec = increase(arr[-1::-1], n)[-1::-1]
		ans = 0
		for i in range(n):
			ans = max(ans, inc[i] + dec[i] - 1)
		return ans


class Solution:

	def bitonic(self, arr, n):
		lis = [1] * n
		lds = [1] * n
		for i in range(1, len(arr)):
			if arr[i - 1] <= arr[i]:
				lis[i] = 1 + lis[i - 1]
		for i in range(len(arr) - 2, -1, -1):
			if arr[i] >= arr[i + 1]:
				lds[i] = 1 + lds[i + 1]
		res = -float('inf')
		for i in range(n):
			res = max(res, lis[i] + lds[i] - 1)
		return res


class Solution:

	def bitonic(self, a, n):
		res = 1
		i = 1
		prev = 0
		next_prev = 0
		i = 1
		while i < n:
			while i < n and a[i] >= a[i - 1]:
				i += 1
			while i < n and a[i] <= a[i - 1]:
				if a[i] < a[i - 1]:
					next_prev = i
				i += 1
			res = max(res, i - prev)
			prev = next_prev
		return res
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.bitonic(arr, n)
		print(ans)
		tc -= 1


class Solution:

	def bitonic(self, arr, n):
		inc = [1] * n
		dec = [1] * n
		for i in range(1, n):
			if arr[i] >= arr[i - 1]:
				inc[i] = inc[i - 1] + 1
		for i in range(n - 2, -1, -1):
			if arr[i] >= arr[i + 1]:
				dec[i] = dec[i + 1] + 1
		res = 0
		for i in range(n):
			res = max(res, dec[i] + inc[i])
		return res - 1
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.bitonic(arr, n)
		print(ans)
		tc -= 1


class Solution:

	def bitonic(self, arr, n):
		inc = [0] * n
		dec = [0] * n
		inc[0] = 1
		dec[n - 1] = 1
		for i in range(1, n):
			if arr[i] >= arr[i - 1]:
				inc[i] = inc[i - 1] + 1
			else:
				inc[i] = 1
		for i in range(n - 2, -1, -1):
			if arr[i] >= arr[i + 1]:
				dec[i] = dec[i + 1] + 1
			else:
				dec[i] = 1
		dp = [0 for _ in range(n)]
		for i in range(n):
			dp[i] = inc[i] + dec[i] - 1
		return max(dp)


class Solution:

	def bitonic(self, arr, n):
		if n == 0:
			return 0
		max_len = 1
		start = 0
		nxt_start = 0
		j = 0
		while j < n - 1:
			while j < n - 1 and arr[j] <= arr[j + 1]:
				j += 1
			while j < n - 1 and arr[j] >= arr[j + 1]:
				if j < n - 1 and arr[j] > arr[j + 1]:
					nxt_start = j + 1
				j += 1
			max_len = max(max_len, j - (start - 1))
			start = nxt_start
		return max_len


class Solution:

	def bitonic(self, arr, n):
		leftinc = [1]
		rghtinc = [1]
		co = 1
		for i in range(1, n):
			if arr[i] >= arr[i - 1]:
				co += 1
			else:
				co = 1
			leftinc.append(co)
		co = 1
		for i in range(n - 2, -1, -1):
			if arr[i] >= arr[i + 1]:
				co += 1
			else:
				co = 1
			rghtinc.append(co)
		rghtinc.reverse()
		maxx = 0
		for i in range(n):
			maxx = max(maxx, leftinc[i] + rghtinc[i] - 1)
		return maxx


class Solution:

	def bitonic(self, arr, n):
		inc = [1] * n
		for i in range(n - 1):
			if arr[i] <= arr[i + 1]:
				inc[i + 1] = inc[i] + 1
		dec = [1] * n
		for i in range(n - 1, 0, -1):
			if arr[i - 1] >= arr[i]:
				dec[i - 1] = dec[i] + 1
		maxi = -1000000000.0
		for i in range(n):
			maxi = max(inc[i] + dec[i] - 1, maxi)
		return maxi


class Solution:

	def bitonic(self, arr, n):
		maxlen = 1
		asc = [0] * n
		asc[0] = maxlen
		dec = [0] * n
		dec[n - 1] = maxlen
		for i in range(1, n, 1):
			if arr[i] >= arr[i - 1]:
				maxlen += 1
				asc[i] = maxlen
			else:
				maxlen = 1
				asc[i] = maxlen
		maxlen = 1
		for i in reversed(range(0, n - 1, 1)):
			if arr[i] >= arr[i + 1]:
				maxlen += 1
				dec[i] = maxlen
			else:
				maxlen = 1
				dec[i] = maxlen
		sum_arr = [asc[i] + dec[i] for i in range(n)]
		return max(sum_arr) - 1


class Solution:

	def bitonic(self, arr, n):
		fw = [1]
		for i in range(1, n):
			if arr[i] >= arr[i - 1]:
				fw.append(fw[i - 1] + 1)
			else:
				fw.append(1)
		bw = [0 for i in range(n)]
		bw[-1] = 1
		for i in range(n - 2, -1, -1):
			if arr[i] >= arr[i + 1]:
				bw[i] = bw[i + 1] + 1
			else:
				bw[i] = 1
		max_length = 0
		for i in range(n):
			max_length = max(max_length, fw[i] + bw[i] - 1)
		return max_length


class Solution:

	def bitonic(self, arr, n):
		a = arr
		min_idx = [i for i in range(n)]
		max_idx = [i for i in range(n)]
		for i in range(1, n):
			if a[i - 1] <= a[i]:
				min_idx[i] = min_idx[i - 1]
		for i in range(n - 2, -1, -1):
			if a[i] >= a[i + 1]:
				max_idx[i] = max_idx[i + 1]
		ans = -1
		for i in range(n):
			temp = max_idx[i] - min_idx[i]
			ans = max(temp, ans)
		return ans + 1


class Solution:

	def bitonic(self, arr, n):
		if n == 0:
			return 0
		max_len = 1
		i = 0
		start = 0
		next_start = 0
		while i < n - 1:
			while i + 1 < n and arr[i] <= arr[i + 1]:
				i += 1
			while i + 1 < n and arr[i + 1] <= arr[i]:
				if i + 1 < n and arr[i + 1] < arr[i]:
					next_start = i + 1
				i += 1
			max_len = max(max_len, i - (start - 1))
			start = next_start
		return max_len


class Solution:

	def bitonic(self, arr, n):
		max_length = 0
		temp_length = 1
		for i in range(n):
			if temp_length > max_length:
				max_length = temp_length
			if n - i < max_length:
				break
			going_up = True
			last_elem = arr[i]
			temp_length = 1
			for j in range(i + 1, n):
				if going_up == True:
					if arr[j] >= last_elem:
						temp_length += 1
					if arr[j] < last_elem:
						temp_length += 1
						going_up = False
					last_elem = arr[j]
					continue
				if going_up == False:
					if arr[j] <= last_elem:
						temp_length += 1
						last_elem = arr[j]
					if arr[j] > last_elem:
						break
		return max_length


class Solution:

	def bitonic(self, arr, n):
		st = 1
		en = 1
		lt = [1 for i in range(n)]
		yt = [1 for i in range(n)]
		for i in range(1, n):
			if arr[i] >= arr[i - 1]:
				st += 1
			else:
				st = 1
			lt[i] = st
		for j in range(n - 2, -1, -1):
			if arr[j] >= arr[j + 1]:
				en += 1
			else:
				en = 1
			yt[j] = en
		mx = 0
		for i in range(n):
			t = lt[i] + yt[i] - 1
			if t > mx:
				mx = t
		return mx


class Solution:

	def bitonic(self, arr, n):
		l = [1] * n
		k = [1] * n
		ans = 0
		arr1 = arr[::-1]
		for i in range(1, n):
			if arr[i] >= arr[i - 1]:
				l[i] = l[i - 1] + 1
		for i in range(1, n):
			if arr1[i] >= arr1[i - 1]:
				k[i] = k[i - 1] + 1
		for i in range(0, n):
			ans = max(l[i] + k[n - i - 1] - 1, ans)
		return ans


class Solution:

	def bitonic(self, arr, n):
		i = 0
		ans = 1
		while i < n:
			count = 0
			while i < n - 1 and arr[i] <= arr[i + 1]:
				i += 1
				count += 1
			while i < n - 1 and arr[i] >= arr[i + 1]:
				i += 1
				count += 1
			ans = max(ans, count + 1)
			if i == n - 1:
				break
			while i >= 1 and arr[i] == arr[i - 1]:
				i -= 1
		return ans


class Solution:

	def bitonic(self, arr, n):
		lis = [1] * n
		lds = [1] * n
		ans = []
		for i in range(1, n):
			if arr[i] >= arr[i - 1]:
				lis[i] = lis[i - 1] + 1
			else:
				lis[i] = 1
		for i in range(n - 2, -1, -1):
			if arr[i] >= arr[i + 1]:
				lds[i] = lds[i + 1] + 1
			else:
				lds[i] = 1
		for i in range(n):
			b = lis[i] + lds[i] - 1
			ans.append(b)
		return max(ans)


class Solution:

	def bitonic(self, arr, n):
		inc = [0] * n
		dec = [0] * n
		inc[0] = 1
		dec[n - 1] = 1
		for i in range(1, n):
			if arr[i] >= arr[i - 1]:
				inc[i] = inc[i - 1] + 1
			else:
				inc[i] = 1
		for i in range(n - 2, -1, -1):
			if arr[i] >= arr[i + 1]:
				dec[i] = dec[i + 1] + 1
			else:
				dec[i] = 1
		maxi = inc[0] + dec[0] - 1
		for i in range(1, n):
			if inc[i] + dec[i] - 1 > maxi:
				maxi = inc[i] + dec[i] - 1
		return maxi


class Solution:

	def bitonic(self, arr, n):
		a = [0] * n
		b = [0] * n
		a[0] = 1
		b[n - 1] = 1
		for i in range(1, n):
			if arr[i] >= arr[i - 1]:
				a[i] = a[i - 1] + 1
			else:
				a[i] = 1
		for i in range(n - 2, -1, -1):
			if arr[i] >= arr[i + 1]:
				b[i] = b[i + 1] + 1
			else:
				b[i] = 1
		maxi = a[0] + b[0] - 1
		for i in range(1, n):
			if a[i] + b[i] - 1 > maxi:
				maxi = a[i] + b[i] - 1
		return maxi


class Solution:

	def bitonic(self, arr, n):
		if n <= 2:
			return n
		start = 0
		end = 0
		ans = 1
		while end + 1 < n:
			while end + 1 < n and arr[end + 1] >= arr[end]:
				end += 1
			newStart = start
			while end + 1 < n and arr[end + 1] <= arr[end]:
				if arr[end + 1] < arr[end]:
					newStart = end + 1
				end += 1
			ans = max(ans, end - start + 1)
			start = newStart
		return ans