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

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 ai>x
, his rating x
 will increase by 1
;
If ai=x
, his rating x
 will remain unchanged;
If ai<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.

Input
Each test contains multiple test cases. The first line of the input contains a single integer t
 (1≤t≤5⋅104
) — 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⋅105
) — the number of contests.

The second line contains n
 integers a1,a2,…,an
 (1≤ai≤n
) — the performance ratings in the contests.

It is guaranteed that the sum of n
 over all test cases does not exceed 3⋅105
.

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

Example
InputCopy
5
6
1 2 3 4 5 6
7
1 2 1 1 1 3 4
1
1
9
9 9 8 2 4 4 3 5 3
10
1 2 3 4 1 3 2 1 1 10
OutputCopy
5
4
0
4
5
Note
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−→−−a1=11−→−−a2=22−→−skip2−→−skip2−→−skip2−→−−a6=33−→−−a7=44

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−→−−a1=91−→−−a2=92−→−−a3=83−→−−a4=22−→−−a5=43−→−−a6=44−→−skip4−→−skip4−→−skip4

In the fifth test case, Kevin's optimal choice is to select the interval [5,9]
.
Bu sualda, #include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ld long double
#define endl '\n'
#define pb push_back
#define speedyboy ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(x) x.begin() , x.end()
#define F first
#define S second
#define pll pair<ll , ll>
#define pss pair<string , string>
#define YES cout << "YES" << endl;
#define NO cout << "NO" << endl;

ll i , j , k;
const ll sz = 5e5 + 5 , INF = 1e9 , MOD = 998244353;
ll a[sz] , cur[sz] , pref[sz];
ll dp[sz][3];

void solve(){
    ll n;
    cin >> n;
    for(i = 1 ; i <= n ; i++){
        cin >> a[i];
    }
    for(i = 0 ; i <= 3 ; i++){
        dp[0][i] = -INF;
    }
    dp[0][0] = 0;
    for(i = 1 ; i <= n ; i++){
        if(dp[i - 1][0] < a[i]){
            dp[i][0] = dp[i - 1][0] + 1;
        }
        else if(dp[i - 1][0] > a[i]){
            dp[i][0] = dp[i - 1][0] - 1;
        }
        else{
            dp[i][0] = dp[i - 1][0];
        }
        dp[i][1] = max(dp[i - 1][1] , dp[i - 1][0]);
        ll x , y;
        if(dp[i - 1][1] < a[i]){
             x = dp[i - 1][1] + 1;
        }
        else if(dp[i - 1][1] > a[i]){
            x = dp[i - 1][1] - 1;
        }
        else{
            x = dp[i - 1][1];
        }
        if(dp[i - 1][2] < a[i]){
             y = dp[i - 1][2] + 1;
        }
        else if(dp[i - 1][2] > a[i]){
            y = dp[i - 1][2] - 1;
        }
        else{
            y = dp[i - 1][2];
        }
        dp[i][2] = max(x , y);
    }
    cout << max(dp[n][1] , dp[n][2]) << endl;
}

signed main(){
    speedyboy;
    ll t = 1;
    cin >> t;
    while(t--){
        solve();
    }
} bu kodu izah eləda, necə olur?dp nəyi göstərir?