[Solution] Robot in a Hallway Codeforces Solution

C. Robot in a Hallway

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

There is a grid, consisting of 2$2$ rows and m$m$ columns. The rows are numbered from 1$1$ to 2$2$ from top to bottom. The columns are numbered from 1$1$ to m$m$ from left to right.

The robot starts in a cell (1,1)$(1,1)$. In one second, it can perform either of two actions:

• move into a cell adjacent by a side: up, right, down or left;
• remain in the same cell.

The robot is not allowed to move outside the grid.

Initially, all cells, except for the cell (1,1)$(1,1)$, are locked. Each cell (i,j)$(i,j)$ contains a value ai,j$a_{i,j}$ — the moment that this cell gets unlocked. The robot can only move into a cell (i,j)$(i,j)$ if at least ai,j$a_{i,j}$ seconds have passed before the move.

The robot should visit all cells without entering any cell twice or more (cell (1,1)$(1,1)$ is considered entered at the start). It can finish in any cell.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 occupied

What is the fastest the robot can achieve that?

Input

The first line contains a single integer t$t$ (1≤t≤104$1\le t\le {10}^4$) — the number of testcases.

The first line of each testcase contains a single integer m$m$ (2≤m≤2⋅105$2\le m\le 2\cdot {10}^5$) — the number of columns of the grid.

The i$i$-th of the next 2$2$ lines contains m$m$ integers ai,1,ai,2,…,ai,m$a_{i,1},a_{i,2},\dots ,a_{i,m}$ (0≤ai,j≤109$0\le a_{i,j}\le {10}^9$) — the moment of time each cell gets unlocked. a1,1=0$a_{1,1}=0$. If ai,j=0$a_{i,j}=0$, then cell (i,j)$(i,j)$ is unlocked from the start.

The sum of m$m$ over all testcases doesn't exceed 2⋅105$2\cdot {10}^5$.

Output

For each testcase, print a single integer — the minimum amount of seconds that the robot can take to visit all cells without entering any cell twice or more.