Masala #V4UCB7MWBA

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.