# C. Robot in a Hallway

Đề bài : https://codeforces.com/contest/1716/problem/C

Nhận xét : chỉ có 2 cách đi là hợp lí, 1 là đi theo hình chữ N (lên, qua phải, xuống, qua phải, lên ...), và đi theo chữ U nằm ngang (đi mãi qua phải tới biên, xuống, qua trái ngược lại).

Cách đi chữ N rất dễ tính, cái khó là cách đi chữ U ngang. Cái này nếu nghĩ kĩ thì chỉ cần xét thằng "max" nhất trong đường đi U ngang. Giải thích ra thì dài dòng nhưng nhận xét đó thật sự đối với mình khá khó để nhìn ra, mình định code cái seg cực dài nhưng khi nằm nghĩ lại thì mới nghĩ ra cách này, code ngắn và gọn hơn rất nhiều.

Code :
::: spoiler

#include<bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i) 
#define rev(i, a, b) for (int i = (a); i >= (b); --i) 
#define ll long long
#define pii pair<int, int>
#define pb push_back
#define fi first
#define pii pair<int, int>
#define se second
#define lb long double

using namespace std; 
const int mxn = 2e5 + 5;
const ll MOD = 998244353;
int n;
ll a[3][mxn], pre[mxn], suf1[mxn], suf2[mxn];

void cal_pre()
{
    pre[1] = a[2][1] + 1;
    rep(i, 2, n) if (i&1)
        pre[i] = max(max(pre[i - 1], a[1][i]) + 1, a[2][i]) + 1;
    else
        pre[i] = max(max(pre[i - 1], a[2][i]) + 1, a[1][i]) + 1;
}

        // ----->
        // <-----
void cal_suf()
{
    ll mx = 0;
    rev(i, n, 1)
    {
        mx -= (i != 1);
        mx = max({mx, a[1][i], a[2][i] - (n - i)*2 - (i != 1)});
        if (mx > pre[i - 1])
            suf1[i] = mx + (n - i + 1)*2 - (i == 1);
        else 
            suf1[i] = pre[i - 1] + (n - i + 1)*2 - (i == 1);
    }

    mx = 0;
    rev(i, n, 1)
    {
        mx -= (i != 1);
        mx = max({mx, a[2][i], a[1][i] - (n - i)*2 - (i != 1)});
        if (mx > pre[i - 1])
            suf2[i] = mx + (n - i + 1)*2 - (i == 1);
        else
            suf2[i] = pre[i - 1] + (n - i + 1)*2 - (i == 1); 
    }
}

int main(){
    //freopen("H:\\file_txt\\input.txt", "r", stdin);
    //freopen("H:\\file_txt\\output.txt", "w", stdout);
    
    int t; cin >> t;
    while(t--)
    { 
        rep(i, 1, 2) rep(j, 0, n) a[i][j] = 0;
        rep(i, 0, n) pre[i] = 0;
        rep(i, 0, n) suf1[i] = 0;
        rep(i, 0, n) suf2[i] = 0;
        cin >> n;
        rep(row, 1, 2) rep(i, 1, n)
            scanf("%lli", &a[row][i]);

        cal_pre();
        cal_suf();

        ll res = min(suf1[1], pre[n]);
        rep(i, 2, n - 1) if (i&1)
            res = min(res, suf1[i]);
        else
            res = min(res, suf2[i]);
        
        cout << res << endl;
    }
    /*rep(i, 1, n) cout << pre[i] << ' '; cout << endl;
    rep(i, 1, n) cout << suf1[i] << ' '; cout << endl;
    rep(i, 1, n) cout << suf2[i] << ' ';*/
}

:::