CF1716C Robot in a Hallway

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 $ (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) $ , are locked. Each cell $ (i, j) $ contains a value $ a_{i,j} $ — the moment that this cell gets unlocked. The robot can only move into a cell $ (i, j) $ 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 $ (1, 1) $ is considered entered at the start). It can finish in any cell. What is the fastest the robot can achieve that?

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 $ (i, j) $ is unlocked from the start. The sum of $ m $ over all testcases doesn't exceed $ 2 \cdot 10^5 $ .

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.