First and last submission
20 removals
69 lines
12 additions
63 lines
# https://www.codechef.com/viewsolution/60594129
# https://www.codechef.com/viewsolution/60638735
# cook your dish here
import sys,os,io
import sys,os,io
import math
import math
from collections import defaultdict
from collections import defaultdict
def ii():
return int(input())
def li():
return list(map(int,input().split()))
if(os.path.exists('input.txt')):
sys.stdin = open("input.txt","r") ; sys.stdout = open("output.txt","w")
else:
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
import bisect
import bisect
def lengthOfLIS(nums):
def lengthOfLIS(nums):
x = []
x = []
temp = [0]*(len(nums))
temp = [0]*(len(nums))
for i in range(len(nums)):
for i in range(len(nums)):
if not x:
if not x:
x.append(nums[i])
x.append(nums[i])
temp[i]=len(x)
temp[i]=len(x)
continue
continue
ind = bisect.bisect_left(x,nums[i])
ind = bisect.bisect_left(x,nums[i])
# replace bisect_left by bisect_right for longes non-dec subsequence
if ind==len(x):
if ind==len(x):
x.append(nums[i])
x.append(nums[i])
else:
else:
x[ind]=nums[i]
x[ind]=nums[i]
temp[i]=len(x)
temp[i]=len(x)
return temp
return temp
def lengthOfLDS(nums):
def lengthOfLDS(nums):
x = []
x = []
temp = [0]*(len(nums))
temp = [0]*(len(nums))
for i in range(len(nums)):
for i in range(len(nums)):
if not x:
if not x:
x.append(nums[i])
x.append(nums[i])
temp[i]=len(x)
temp[i]=len(x)
continue
continue
ind = bisect.bisect_left(x,nums[i])
ind = bisect.bisect_left(x,nums[i])
# replace bisect_left by bisect_right for longes non-dec subsequence
if ind==len(x):
if ind==len(x):
x.append(nums[i])
x.append(nums[i])
else:
else:
x[ind]=nums[i]
x[ind]=nums[i]
temp[i]=len(x)
temp[i]=len(x)
return temp[::-1]
return temp[::-1]
def solve():
def solve():
n = ii()
n = int(input())
l = li()
l = list(map(int,input().split()))
a = lengthOfLIS(l)
a = lengthOfLIS(l)
for i in range(n):
for i in range(n):
l[i]=-l[i]
l[i]=-l[i]
l = l[::-1]
l = l[::-1]
b = lengthOfLDS(l)
b = lengthOfLDS(l)
ans = 0
ans = 0
for i in range(n-1):
for i in range(n-1):
ans=max(ans,a[i]+b[i+1])
ans=max(ans,a[i]+b[i+1])
print(ans)
print(ans)
t = 1
t = ii()
t = int(input())
for _ in range(t):
for i in range(t):
solve()
solve()