## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## [Solution] LIS or Reverse LIS? Codeforces Solution | Codeforces Problem Solution 2022

C. LIS or Reverse LIS?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $a$ of $n$ positive integers.

Let $\text{LIS}\left(a\right)$ denote the length of longest strictly increasing subsequence of $a$. For example,

• $\text{LIS}\left(\left[2,\underset{_}{1},1,\underset{_}{3}\right]\right)$ = $2$.
• $\text{LIS}\left(\left[\underset{_}{3},\underset{_}{5},\underset{_}{10},\underset{_}{20}\right]\right)$ = $4$.
• $\text{LIS}\left(\left[3,\underset{_}{1},\underset{_}{2},\underset{_}{4}\right]\right)$ = $3$.

We define array ${a}^{\prime }$ as the array obtained after reversing the array $a$ i.e. ${a}^{\prime }=\left[{a}_{n},{a}_{n-1},\dots ,{a}_{1}\right]$.

The beauty of array $a$ is defined as $min\left(\text{LIS}\left(a\right),\text{LIS}\left({a}^{\prime }\right)\right)$.

Input

The input consists of multiple test cases. The first line contains a single integer $t$ $\left(1\le t\le {10}^{4}\right)$  — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer $n$ $\left(1\le n\le 2\cdot {10}^{5}\right)$  — the length of array $a$.

The second line of each test case contains $n$ integers ${a}_{1},{a}_{2},\dots ,{a}_{n}$ $\left(1\le {a}_{i}\le {10}^{9}\right)$  — the elements of the array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot {10}^{5}$.

Output

For each test case, output a single integer  — the maximum possible beauty of $a$ after rearranging its elements arbitrarily.