CF2029C New Rating

Hello, Codeforces Forcescode! Kevin used to be a participant of Codeforces. Recently, the KDOI Team has developed a new Online Judge called Forcescode. Kevin has participated in $ n $ contests on Forcescode. In the $ i $ -th contest, his performance rating is $ a_i $ . Now he has hacked into the backend of Forcescode and will select an interval $ [l,r] $ ( $ 1\le l\le r\le n $ ), then skip all of the contests in this interval. After that, his rating will be recalculated in the following way: - Initially, his rating is $ x=0 $ ; - For each $ 1\le i\le n $ , after the $ i $ -th contest, - If $ l\le i\le r $ , this contest will be skipped, and the rating will remain unchanged; - Otherwise, his rating will be updated according to the following rules: - If $ a_i>x $ , his rating $ x $ will increase by $ 1 $ ; - If $ a_i=x $ , his rating $ x $ will remain unchanged; - If $ a_i

Each test contains multiple test cases. The first line of the input contains a single integer $ t $ ( $ 1\le t\le 5\cdot 10^4 $ ) — the number of test cases. The description of test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1\le n\le 3\cdot 10^5 $ ) — the number of contests. The second line contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ 1\le a_i\le n $ ) — the performance ratings in the contests. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 3 \cdot 10^5 $ .

For each test case, output a single integer — the maximum possible rating after the recalculation if Kevin chooses the interval optimally.

In the first test case, Kevin must skip at least one contest. If he chooses any interval of length $1$, his rating after the recalculation will be equal to $5$. In the second test case, Kevin's optimal choice is to select the interval $[3, 5]$. During the recalculation, his rating changes as follows: $$ 0 \xrightarrow{a_1 = 1} 1 \xrightarrow{a_2 = 2} 2 \xrightarrow{\mathtt{skip}} 2 \xrightarrow{\mathtt{skip}} 2 \xrightarrow{\mathtt{skip}} 2 \xrightarrow{a_6 = 3} 3 \xrightarrow{a_7 = 4} 4 $$ In the third test case, Kevin must skip the only contest, so his rating will remain at the initial value of $0$. In the fourth test case, Kevin's optimal choice is to select the interval $[7, 9]$ . During the recalculation, his rating changes as follows: $$ 0 \xrightarrow{a_1 = 9} 1 \xrightarrow{a_2 = 9} 2 \xrightarrow{a_3 = 8} 3 \xrightarrow{a_4 = 2} 2 \xrightarrow{a_5 = 4} 3 \xrightarrow{a_6 =4 } 4 \xrightarrow{\mathtt{skip}} 4 \xrightarrow{\mathtt{skip}} 4 \xrightarrow{\mathtt{skip}} 4 $$ In the fifth test case, Kevin's optimal choice is to select the interval $[5, 9]$.