## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [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$ rows and $m$ columns. The rows are numbered from $1$ to $2$ from top to bottom. The columns are numbered from $1$ to $m$ from left to right.

The robot starts in a cell $\left(1,1\right)$. 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 $\left(1,1\right)$, are locked. Each cell $\left(i,j\right)$ contains a value ${a}_{i,j}$ — the moment that this cell gets unlocked. The robot can only move into a cell $\left(i,j\right)$ if at least ${a}_{i,j}$ seconds have passed before the move.

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

Solution Click Below:-  👉

👇👇👇👇👇

occupied

What is the fastest the robot can achieve that?

Input

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

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

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

The sum of $m$ over all testcases doesn't exceed $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.