write a go solution for C. New Ratingtime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputHello, 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<=l<=r<=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<=i<=n, after the i-th contest,   If l<=i<=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<x, his rating x will decrease by 1.   You have to help Kevin to find his maximum possible rating after the recalculation if he chooses the interval [l,r] optimally. Note that Kevin has to skip at least one contest.InputEach test contains multiple test cases. The first line of the input contains a single integer t (1<=t<=5*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<=n<=3*10^5) — the number of contests.The second line contains n integers a_1,a_2,ldots,a_n (1<=a_i<=n) — the performance ratings in the contests.It is guaranteed that the sum of n over all test cases does not exceed 3*10^5.OutputFor each test case, output a single integer — the maximum possible rating after the recalculation if Kevin chooses the interval optimally.ExampleInput561 2 3 4 5 671 2 1 1 1 3 41199 9 8 2 4 4 3 5 3101 2 3 4 1 3 2 1 1 10Output5
4
0
4
5
NoteIn 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].. Output only the code with no comments, explanation, or additional text.