Chef received an array A of N integers as a valentine's day present. He wants to maximize the length of the longest strictly increasing subsequence by choosing a subarray and adding a fixed integer X to all its elements.

More formally, Chef wants to maximize the length of the [longest strictly increasing subsequence] of A by performing the following operation at most once:

Pick 3 integers L, R and X \ (1 ≤ L ≤ R ≤ N, \ X \in \mathbb{Z}) and assign A_{i} := A_{i} + X \ \forall \ i \in [L, R].

Find the length of the longest strictly increasing sequence Chef can obtain after performing the operation at most once.

------ Input Format ------ 

- The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains one integer N, the size of the array.
- The next line contains N space-separated integers, where the i^{th} integer denotes A_{i}.

------ Output Format ------ 

For each test case, print a single line containing one integer ― the length of the longest strictly increasing sequence Chef can obtain.

------ Constraints ------ 

$1 ≤ T ≤ 10^{3}$
$1 ≤ N ≤ 2 \times 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
3
3
1 2 1
5
1 5 8 6 9
4
1 2 2 1

----- Sample Output 1 ------ 
3
5
3

----- explanation 1 ------ 
Test case $1$: Chef can pick $(L,R,X)=(3,3,2)$. On performing the operation, $A$ becomes $[1,2,3]$. The LIS of the updated array has length $3$. The elements of the LIS are $[1,2,3]$.

Test case $2$: Chef can pick $(L,R,X)=(2,3,-3)$. On performing the operation, $A$ becomes $[1,2,5,6,9]$. The LIS of the updated array has length $5$. The elements of the LIS are $[1,2,5,6,9]$.

Test case $3$: Chef can pick $(L,R,X)=(4,4,4)$. On performing the operation, $A$ becomes $[1,2,2,5]$. The LIS of the updated array has length $3$. The elements of the LIS are $[1,2,5]$.

Difficulty: HARD
Tags: Complete search
Skill types: Complete search

Starter code:

Solutions:
def lis_right_dp(nums):
	n = len(nums)
	maxv = [0] * (n + 1)
	(pr, maxv[1]) = (1, nums[-1])
	dp = [0] * n
	dp[-1] = 1
	for j in range(n - 2, -1, -1):
		(l, r) = (1, pr)
		while r - l > 2:
			m = (r + l) // 2
			if nums[j] >= maxv[m]:
				r = m - 1
			else:
				l = m
		x = 1
		for p in range(r, l - 1, -1):
			if maxv[p] > nums[j]:
				x = p + 1
				break
		maxv[x] = max(maxv[x], nums[j])
		dp[j] = x
		pr = max(pr, x)
	return dp

def lis_left_dp(nums):
	n = len(nums)
	minv = [1000000000.0] * (n + 1)
	(pr, minv[1]) = (1, nums[0])
	dp = [0] * n
	dp[0] = 1
	for j in range(1, n):
		(l, r) = (1, pr)
		while r - l > 2:
			m = (r + l) // 2
			if nums[j] < minv[m]:
				r = m - 1
			else:
				l = m
		x = 1
		for p in range(r, l - 1, -1):
			if minv[p] < nums[j]:
				x = p + 1
				break
		minv[x] = min(minv[x], nums[j])
		dp[j] = x
		pr = max(pr, x)
	return dp
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = [-x for x in a][::-1]
	(g, h) = (lis_left_dp(a), lis_right_dp(a))
	for j in range(n - 2, -1, -1):
		h[j] = max(h[j], h[j + 1])
	(p, v) = (max(g), g[0])
	for j in range(n - 1):
		v = max(g[j], v)
		p = max(p, v + h[j + 1])
	print(p)


from bisect import bisect_left

def solve():
	n = int(input())
	a = list(map(int, input().split(' ')))
	dp1 = [1] * n
	dp2 = [1] * n
	st = []
	for i in range(n):
		it = bisect_left(st, a[i])
		if it == len(st):
			st.append(a[i])
		else:
			st[it] = a[i]
		dp1[i] = len(st)
	st = []
	for i in range(n - 1, -1, -1):
		it = bisect_left(st, -1 * a[i])
		if it == len(st):
			st.append(-1 * a[i])
		else:
			st[it] = -1 * a[i]
		dp2[i] = len(st)
	ans = float('-inf')
	for i in range(1, n):
		ans = max(ans, dp1[i - 1] + dp2[i])
	print(ans)
for _ in range(int(input())):
	solve()


from bisect import *
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	(l, r) = ([0] * n, [0] * n)
	temp = []
	for (i, vl) in enumerate(a):
		ind = bisect_left(temp, vl, 0, len(temp))
		if ind == len(temp):
			temp.append(vl)
		else:
			temp[ind] = vl
		l[i] = len(temp)
	temp = []
	for (i, vl) in enumerate(a[::-1], start=1):
		ind = bisect_left(temp, -vl, 0, len(temp))
		if ind == len(temp):
			temp.append(-vl)
		else:
			temp[ind] = -vl
		r[-i] = len(temp)
	ans = l[-1]
	for i in range(1, n):
		ans = max(ans, l[i - 1] + r[i])
	print(ans)


import bisect
import math
from collections import defaultdict

def lengthOfLIS(nums):
	x = []
	temp = [0] * len(nums)
	for i in range(len(nums)):
		if not x:
			x.append(nums[i])
			temp[i] = len(x)
			continue
		ind = bisect.bisect_left(x, nums[i])
		if ind == len(x):
			x.append(nums[i])
		else:
			x[ind] = nums[i]
		temp[i] = len(x)
	return temp

def lengthOfLDS(nums):
	x = []
	temp = [0] * len(nums)
	for i in range(len(nums)):
		if not x:
			x.append(nums[i])
			temp[i] = len(x)
			continue
		ind = bisect.bisect_left(x, nums[i])
		if ind == len(x):
			x.append(nums[i])
		else:
			x[ind] = nums[i]
		temp[i] = len(x)
	return temp[::-1]

def solve(n, l):
	a = lengthOfLIS(l)
	for i in range(n):
		l[i] = -l[i]
	l = l[::-1]
	b = lengthOfLDS(l)
	ans = 0
	for i in range(n - 1):
		ans = max(ans, a[i] + b[i + 1])
	print(ans)
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	solve(n, a)


import bisect

def LDS(arr):
	x = []
	temp = [0] * len(arr)
	for i in range(len(arr)):
		if not x:
			x.append(arr[i])
			temp[i] = len(x)
			continue
		idx = bisect.bisect_left(x, arr[i])
		if idx == len(x):
			x.append(arr[i])
		else:
			x[idx] = arr[i]
		temp[i] = len(x)
	return temp[::-1]

def LIS(arr):
	x = []
	temp = [0] * len(arr)
	for i in range(len(arr)):
		if not x:
			x.append(arr[i])
			temp[i] = len(x)
			continue
		idx = bisect.bisect_left(x, arr[i])
		if idx == len(x):
			x.append(arr[i])
		else:
			x[idx] = arr[i]
		temp[i] = len(x)
	return temp
t = int(input())
for k in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	a = LIS(arr)
	for i in range(n):
		arr[i] = -1 * arr[i]
	arr = arr[::-1]
	b = LDS(arr)
	res = 0
	for i in range(n - 1):
		res = max(res, a[i] + b[i + 1])
	print(res)


from math import inf
from collections import *
import math, os, sys, heapq, bisect, random
from functools import lru_cache
from itertools import *

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def inpu():
	return int(inp())

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())
(M, M1) = (1000000007, 998244353)

def main():
	how_much_noob_I_am = 1
	how_much_noob_I_am = inpu()
	for _ in range(how_much_noob_I_am):
		n = inpu()
		arr = lis()

		def fun(arr):
			l = []
			temp = [0] * n
			for i in range(len(arr)):
				p = bisect.bisect_left(l, arr[i])
				if p == len(l):
					l.append(arr[i])
				l[p] = arr[i]
				temp[i] = len(l)
			return temp
		temp = fun(arr)
		for i in range(n):
			arr[i] = -arr[i]
		arr.reverse()
		temp2 = fun(arr)
		temp2.reverse()
		ans = 0
		for i in range(n - 1):
			ans = max(ans, temp[i] + temp2[i + 1])
		print(ans)
main()


from bisect import bisect_left

def lis(a):
	l = [0] * len(a)
	mx = 0
	ans = []
	for i in range(len(a)):
		x = bisect_left(ans, a[i])
		if x >= len(ans):
			ans.append(a[i])
		else:
			ans[x] = a[i]
		mx = max(mx, x)
		l[i] = mx
	return l
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	lis1 = lis(a)
	lis2 = list(map(lambda x: -x, a))[::-1]
	lis2 = lis(lis2)[::-1]
	ans = 1
	for i in range(n - 1):
		ans = max(ans, lis1[i] + lis2[i + 1] + 2)
	print(ans)


from bisect import bisect_left

def lis(n):
	q = []
	store = [0] * len(n)
	for i in range(len(n)):
		if not q:
			q.append(n[i])
			store[i] = len(q)
			continue
		index = bisect_left(q, n[i])
		if index == len(q):
			q.append(n[i])
		else:
			q[index] = n[i]
		store[i] = len(q)
	return store
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	lis1 = lis(a)
	lis2 = list(map(lambda x: -x, a))[::-1]
	lis2 = lis(lis2)[::-1]
	ans = 1
	for i in range(n - 1):
		ans = max(ans, lis1[i] + lis2[i + 1])
	print(ans)


import bisect
for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	prefix = [0 for i in range(n)]
	suffix = [0 for i in range(n)]
	temp = []
	for i in range(n):
		idx = bisect.bisect_left(temp, lst[i])
		if idx == len(temp):
			temp.append(lst[i])
		else:
			temp[idx] = lst[i]
		prefix[i] = len(temp)
	temp = []
	for i in range(n - 1, -1, -1):
		idx = bisect.bisect_left(temp, -lst[i])
		if idx == len(temp):
			temp.append(-lst[i])
		else:
			temp[idx] = -lst[i]
		suffix[i] = len(temp)
	maxi = 0
	for i in range(1, n):
		maxi = max(maxi, prefix[i - 1] + suffix[i])
	print(maxi)


try:
	import bisect

	def lis(nums):
		x = []
		temp = [0] * len(nums)
		for i in range(len(nums)):
			if not x:
				x.append(nums[i])
				temp[i] = len(x)
				continue
			ind = bisect.bisect_left(x, nums[i])
			if ind == len(x):
				x.append(nums[i])
			else:
				x[ind] = nums[i]
			temp[i] = len(x)
		return temp
	for tc in range(int(input())):
		n = int(input())
		arr = list(map(int, input().split()))
		ans = -1
		li = lis(arr)
		arr = [-i for i in arr]
		di = lis(arr[::-1])[::-1]
		for i in range(n - 1):
			ans = max(ans, li[i] + di[i + 1])
		print(ans)
except EOFError:
	pass


nmbr = lambda : int(input())
lst = lambda : list(map(int, input().split()))
from bisect import bisect_left
from collections import deque

def find_lis(a):
	lis = []
	dp = []
	for i in range(n):
		v = a[i]
		if not lis or v > lis[-1]:
			lis += [v]
		else:
			pos = bisect_left(lis, v)
			lis[pos] = v
		dp += [len(lis)]
	return dp

def find_lds(a):
	lis = deque()
	dp = []
	for i in range(n):
		v = a[i]
		if not lis or v < lis[0]:
			lis.appendleft(v)
		else:
			pos = bisect_left(lis, v)
			if pos >= len(lis) or lis[pos] != v:
				pos -= 1
			lis[pos] = v
		dp += [len(lis)]
	return dp[::-1]
for _ in range(nmbr()):
	n = nmbr()
	a = lst()
	pre = find_lis(a)
	suf = find_lds(a[::-1])
	ans = suf[0]
	for i in range(n - 1):
		ans = max(ans, pre[i] + suf[i + 1])
	print(ans)


import os
import bisect
import math
import io
import sys
from collections import defaultdict

def khdfjkhsdfkh(nums):
	x = []
	temp = len(nums) * [0]
	for i in range(len(nums)):
		if not x:
			x.append(nums[i])
			temp[i] = len(x)
			continue
		ind = bisect.bisect_left(x, nums[i])
		if ind == len(x):
			x.append(nums[i])
		else:
			x[ind] = nums[i]
		temp[i] = len(x)
	return temp

def lengthOfLDS(nums):
	x = []
	temp = [0] * len(nums)
	for i in range(len(nums)):
		if not x:
			x.append(nums[i])
			temp[i] = len(x)
			continue
		ind = bisect.bisect_left(x, nums[i])
		if ind == len(x):
			x.append(nums[i])
		else:
			x[ind] = nums[i]
		temp[i] = len(x)
	return temp[::-1]

def solve():
	n = int(input())
	l = list(map(int, input().split()))
	a = khdfjkhsdfkh(l)
	for i in range(n):
		l[i] = -l[i]
	l = l[::-1]
	b = lengthOfLDS(l)
	ans = 0
	for i in range(n - 1):
		ans = max(ans, a[i] + b[i + 1])
	print(ans)
t = int(input())
for _ in range(t):
	solve()


import sys, os, io
import math
from collections import defaultdict
import bisect

def LIS(arr):
	lst1 = []
	tmp = [0] * len(arr)
	for i in range(len(arr)):
		if not lst1:
			lst1.append(arr[i])
			tmp[i] = len(lst1)
			continue
		ind = bisect.bisect_left(lst1, arr[i])
		if ind == len(lst1):
			lst1.append(arr[i])
		else:
			lst1[ind] = arr[i]
		tmp[i] = len(lst1)
	return tmp

def LDS(arr):
	lst1 = []
	tmp = [0] * len(arr)
	for i in range(len(arr)):
		if not lst1:
			lst1.append(arr[i])
			tmp[i] = len(lst1)
			continue
		ind = bisect.bisect_left(lst1, arr[i])
		if ind == len(lst1):
			lst1.append(arr[i])
		else:
			lst1[ind] = arr[i]
		tmp[i] = len(lst1)
	return tmp[::-1]
test = int(input())
for _ in range(test):
	n = int(input())
	lst = list(map(int, input().split()))
	tmp1 = LIS(lst)
	for i in range(n):
		lst[i] = -lst[i]
	lst = lst[::-1]
	tmp2 = LDS(lst)
	result = 0
	for i in range(n - 1):
		result = max(result, tmp1[i] + tmp2[i + 1])
	print(result)


try:
	import bisect

	def lengthOfLIS(nums):
		x = []
		temp = [0] * len(nums)
		for i in range(len(nums)):
			if not x:
				x.append(nums[i])
				temp[i] = len(x)
				continue
			ind = bisect.bisect_left(x, nums[i])
			if ind == len(x):
				x.append(nums[i])
			else:
				x[ind] = nums[i]
			temp[i] = len(x)
		return temp

	def lengthOfLDS(nums):
		x = []
		temp = [0] * len(nums)
		for i in range(len(nums)):
			if not x:
				x.append(nums[i])
				temp[i] = len(x)
				continue
			ind = bisect.bisect_left(x, nums[i])
			if ind == len(x):
				x.append(nums[i])
			else:
				x[ind] = nums[i]
			temp[i] = len(x)
		return temp[::-1]
	t = int(input())
	while t:
		n = int(input())
		l = list(map(int, input().split()))
		a = lengthOfLIS(l)
		for i in range(n):
			l[i] = -l[i]
		l = l[::-1]
		b = lengthOfLDS(l)
		ans = 0
		for i in range(n - 1):
			ans = max(ans, a[i] + b[i + 1])
		print(ans)
except:
	pass


import bisect

def loLIS(nums):
	x = []
	temp = [0] * len(nums)
	for i in range(len(nums)):
		if not x:
			x.append(nums[i])
			temp[i] = len(x)
			continue
		ind = bisect.bisect_left(x, nums[i])
		if ind == len(x):
			x.append(nums[i])
		else:
			x[ind] = nums[i]
		temp[i] = len(x)
	return temp

def loLDS(nums):
	x = []
	temp = [0] * len(nums)
	for i in range(len(nums)):
		if not x:
			x.append(nums[i])
			temp[i] = len(x)
			continue
		ind = bisect.bisect_left(x, nums[i])
		if ind == len(x):
			x.append(nums[i])
		else:
			x[ind] = nums[i]
		temp[i] = len(x)
	return temp[::-1]
T = int(input())
for z in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	A = A[:N]
	a = loLIS(A)
	for i in range(N):
		A[i] = -A[i]
	A = A[::-1]
	b = loLDS(A)
	ans = 0
	for i in range(N - 1):
		ans = max(ans, a[i] + b[i + 1])
	print(ans)


def subsequence(seq):
	if not seq:
		return []
	answer = [1]
	M = [None] * len(seq)
	P = [None] * len(seq)
	L = 1
	M[0] = 0
	for i in range(1, len(seq)):
		lower = 0
		upper = L
		if seq[M[upper - 1]] < seq[i]:
			j = upper
		else:
			while upper - lower > 1:
				mid = (upper + lower) // 2
				if seq[M[mid - 1]] < seq[i]:
					lower = mid
				else:
					upper = mid
			j = lower
		P[i] = M[j - 1]
		if j == L or seq[i] < seq[M[j]]:
			M[j] = i
			L = max(L, j + 1)
		answer.append(L)
	return answer
T = int(input())
for _ in range(T):
	N = int(input())
	a = list(map(int, input().split()))
	left = subsequence(a)
	a.reverse()
	a = [-x for x in a]
	right = subsequence(a)
	M = 0
	for i in range(N - 1):
		if left[i] + right[N - 2 - i] > M:
			M = left[i] + right[N - 2 - i]
	print(M)


import sys, os, io, math
from collections import defaultdict
import bisect

def lengthLis(nums):
	x = []
	tempo = [0] * len(nums)
	for i in range(len(nums)):
		if not x:
			x.append(nums[i])
			tempo[i] = len(x)
			continue
		ind = bisect.bisect_left(x, nums[i])
		if ind == len(x):
			x.append(nums[i])
		else:
			x[ind] = nums[i]
		tempo[i] = len(x)
	return tempo

def lengthLds(nums):
	x = []
	tempo = [0] * len(nums)
	for i in range(len(nums)):
		if not x:
			x.append(nums[i])
			tempo[i] = len(x)
			continue
		ind = bisect.bisect_left(x, nums[i])
		if ind == len(x):
			x.append(nums[i])
		else:
			x[ind] = nums[i]
		tempo[i] = len(x)
	return tempo[::-1]

def func():
	n = int(input())
	l = list(map(int, input().split()))
	a = lengthLis(l)
	for i in range(n):
		l[i] = -l[i]
	l = l[::-1]
	b = lengthLds(l)
	ans = 0
	for i in range(n - 1):
		ans = max(ans, a[i] + b[i + 1])
	print(ans)
t = 1
t = int(input())
for _ in range(t):
	func()


def ii():
	return int(input())

def li():
	return list(map(int, input().split()))
import bisect

def lengthOfLIS(nums):
	y = []
	t = [0] * len(nums)
	for i in range(len(nums)):
		if not y:
			y.append(nums[i])
			t[i] = len(y)
			continue
		ind = bisect.bisect_left(y, nums[i])
		if ind == len(y):
			y.append(nums[i])
		else:
			y[ind] = nums[i]
		t[i] = len(y)
	return t

def lengthOfLDS(nums):
	x = []
	temp = [0] * len(nums)
	for i in range(len(nums)):
		if not x:
			x.append(nums[i])
			temp[i] = len(x)
			continue
		ind = bisect.bisect_left(x, nums[i])
		if ind == len(x):
			x.append(nums[i])
		else:
			x[ind] = nums[i]
		temp[i] = len(x)
	return temp[::-1]

def solve():
	n = ii()
	l = li()
	a = lengthOfLIS(l)
	for i in range(n):
		l[i] = -l[i]
	l = l[::-1]
	b = lengthOfLDS(l)
	ans = 0
	for i in range(n - 1):
		ans = max(ans, a[i] + b[i + 1])
	print(ans)
t = 1
t = ii()
for _ in range(t):
	solve()


import bisect

def solverl1(n1):
	z = []
	rm = [0] * len(n1)
	for xjk in range(len(n1)):
		if not z:
			z.append(n1[xjk])
			rm[xjk] = len(z)
			continue
		pak = bisect.bisect_left(z, n1[xjk])
		if pak == len(z):
			z.append(n1[xjk])
		else:
			z[pak] = n1[xjk]
		rm[xjk] = len(z)
	return rm

def solverl2(n2):
	z = []
	rm = [0] * len(n2)
	for xjk in range(len(n2)):
		if not z:
			z.append(n2[xjk])
			rm[xjk] = len(z)
			continue
		pak = bisect.bisect_left(z, n2[xjk])
		if pak == len(z):
			z.append(n2[xjk])
		else:
			z[pak] = n2[xjk]
		rm[xjk] = len(z)
	return rm[::-1]

def answer():
	xk = int(input())
	a = [int(i) for i in input().split()]
	mb = solverl1(a)
	for i in range(xk):
		a[i] = -a[i]
	a = a[::-1]
	wh = solverl2(a)
	sol = 0
	for i in range(xk - 1):
		sol = max(sol, mb[i] + wh[i + 1])
	print(sol)
t = int(input())
for _ in range(t):
	answer()


import bisect

def length1(nums):
	x = []
	temp = [0] * len(nums)
	for i in range(len(nums)):
		if not x:
			x.append(nums[i])
			temp[i] = len(x)
			continue
		ind = bisect.bisect_left(x, nums[i])
		if ind == len(x):
			x.append(nums[i])
		else:
			x[ind] = nums[i]
		temp[i] = len(x)
	return temp

def length2(nums):
	x = []
	temp = [0] * len(nums)
	for i in range(len(nums)):
		if not x:
			x.append(nums[i])
			temp[i] = len(x)
			continue
		ind = bisect.bisect_left(x, nums[i])
		if ind == len(x):
			x.append(nums[i])
		else:
			x[ind] = nums[i]
		temp[i] = len(x)
	return temp[::-1]

def solve():
	n = int(input())
	l = list(map(int, input().split()))
	a = length1(l)
	for i in range(n):
		l[i] = -l[i]
	l = l[::-1]
	b = length2(l)
	ans = 0
	for i in range(n - 1):
		ans = max(ans, a[i] + b[i + 1])
	print(ans)
t = int(input())
for i in range(t):
	solve()


import sys, os, io
import math
from collections import defaultdict

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))
import bisect

def lengthLIS(nums):
	y = []
	temp = [0] * len(nums)
	for i in range(len(nums)):
		if not y:
			y.append(nums[i])
			temp[i] = len(y)
			continue
		ind = bisect.bisect_left(y, nums[i])
		if ind == len(y):
			y.append(nums[i])
		else:
			y[ind] = nums[i]
		temp[i] = len(y)
	return temp

def lengthLDS(nums):
	y = []
	temp = [0] * len(nums)
	for i in range(len(nums)):
		if not y:
			y.append(nums[i])
			temp[i] = len(y)
			continue
		ind = bisect.bisect_left(y, nums[i])
		if ind == len(y):
			y.append(nums[i])
		else:
			y[ind] = nums[i]
		temp[i] = len(y)
	return temp[::-1]

def solve():
	n = ii()
	l = li()
	a = lengthLIS(l)
	for i in range(n):
		l[i] = -l[i]
	l = l[::-1]
	b = lengthLDS(l)
	ans = 0
	for i in range(n - 1):
		ans = max(ans, a[i] + b[i + 1])
	print(ans)
t = 1
t = ii()
for _ in range(t):
	solve()


import bisect

def llis(arr, s):
	if s == 0:
		l1 = []
		l2 = []
		n = len(arr)
		for i in range(0, n):
			l2.append(0)
		for i in range(len(arr)):
			if not l1:
				l1.append(arr[i])
				l2[i] = len(l1)
				continue
			ans = bisect.bisect_left(l1, arr[i])
			if ans == len(l1):
				l1.append(arr[i])
			else:
				l1[ans] = arr[i]
			l2[i] = len(l1)
		return l2
	else:
		l1 = []
		l2 = []
		n = len(arr)
		for i in range(0, n):
			l2.append(0)
		for i in range(0, n):
			if not l1:
				l1.append(arr[i])
				l2[i] = len(l1)
				continue
			ans = bisect.bisect_left(l1, arr[i])
			if ans == len(l1):
				l1.append(arr[i])
			else:
				l1[ans] = arr[i]
			l2[i] = len(l1)
		return l2[::-1]
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	l1 = llis(arr, 0)
	for i in range(n):
		arr[i] = -arr[i]
	arr = arr[::-1]
	l2 = llis(arr, 1)
	ans = 0
	for i in range(n - 1):
		ans = max(ans, l1[i] + l2[i + 1])
	print(ans)


import sys, os, io
import math
from collections import defaultdict
import bisect

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))

def lengthOfLIS(nums):
	x = []
	temp = [0] * len(nums)
	length = len(nums)
	it = 0
	while it < length:
		if not x:
			x.append(nums[it])
			temp[it] = len(x)
			continue
		ind = bisect.bisect_left(x, nums[it])
		if ind == len(x):
			x.append(nums[it])
		else:
			x[ind] = nums[it]
		temp[it] = len(x)
		it += 1
	return temp

def lengthOfLDS(nums):
	x = []
	temp = [0] * len(nums)
	for i in range(len(nums)):
		if not x:
			x.append(nums[i])
			temp[i] = len(x)
			continue
		ind = bisect.bisect_left(x, nums[i])
		if ind == len(x):
			x.append(nums[i])
		else:
			x[ind] = nums[i]
		temp[i] = len(x)
	return temp[::-1]

def solve():
	n = ii()
	l = li()
	a = lengthOfLIS(l)
	i = 0
	while i < n:
		l[i] = -l[i]
		i += 1
	l = l[::-1]
	b = lengthOfLDS(l)
	ans = 0
	j = 0
	while j < n - 1:
		ans = max(ans, a[j] + b[j + 1])
		j += 1
	print(ans)
t = 1
t = ii()
for _ in range(t):
	solve()