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 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 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. 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 ch