Masala E

Sizga $n$ ta elementdan tashkil topgan $a$ massiv beriladi.

$L(a)$ - bu funksiya $a$ massivning eng uzun ortib boruvchi ketma-ketligi uzunligini hisoblaydi. Masalan:

• $L([2,1,1,3]) = 2$ ketma-ketlik $[1,3]$;
• $L([7,2,9,1,11])=3$ ketma-ketlik $[7,9,11]$;
• $L([3,1,2,4])=3$ ketma-ketlik $[1,2,4]$.

Massivni $a'$ hisoblash uchun biz uni teskari tartibda joylashtirib chiqamiz, ya'ni $a'=[a_n,a_{n-1},...,a_1]$.

Sizning vazifangiz massivni istalgan tartibda elementlarini qayta tartibga solganingizdan so'ng $min(L(a),L(a'))$ ning qiymatini hisoblashdan iborat, faqat ushbu qiymat maksimal bo'lsin.

Kirish faylining dastlabki satrda $t(1\leq t\leq 10^4)$ testlar soni beriladi. Kiyingi satrlarda sizga $t$ ta test beriladi, har bir testning dastlabki satrda $n(1\leq n\leq 10^5)$massiv elementlari soni va kiyingi satrda $n$ ta son $a_1,a_2,...,a_n(1\leq a_i\leq 10^9)$ beriladi.

Barcha kiruvchi ma'lumotlar soni $10^6$ dan oshmaydi.

Chiqish faylida har bir test uchun masalani yechimini alohida satrlarda chop eting.