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?


-----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 $(i, j)$ 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.


-----Examples-----

Input
4
3
0 0 1
4 3 2
5
0 4 8 12 16
2 6 10 14 18
4
0 10 10 10
10 10 10 10
2
0 0
0 0
Output
5
19
17
3


-----Note-----

None

Difficulty: HARD
Tags: Sorting

Implementation

Greedy algorithms

Dynamic programming

Data structures
Skill types: Dynamic programming

Sorting

Data structures

Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	c = int(input())
	a = [list(map(int, input().split())) for _ in range(2)]
	a[0][0] = -1
	pos = (0, 0)
	dync = [0 for _ in range(c)]
	y = 0
	for x in range(c - 1):
		y = not y
		curr = max(a[y][x] + 2, a[y][x + 1] + 1)
		dync[x + 1] = max(curr, dync[x] + 2)
	top = list(range(0, c, 2))
	latestTime = 0
	for x in top[::-1]:
		dist = (c - x) * 2 - 1
		if x + 1 < c:
			curr = max(a[0][x] + dist + 1, a[0][x + 1] + dist, a[1][x] + 1, a[1][x + 1] + 2)
		else:
			curr = max(a[0][x] + 2, a[1][x] + 1)
		latestTime = max(latestTime + 2, curr)
		dync[x] = max(dync[x] + dist, latestTime)
	bottom = list(range(1, c, 2))
	latestTime = 0
	for x in bottom[::-1]:
		dist = (c - x) * 2 - 1
		if x + 1 < c:
			curr = max(a[1][x] + dist + 1, a[1][x + 1] + dist, a[0][x] + 1, a[0][x + 1] + 2)
		else:
			curr = max(a[1][x] + 2, a[0][x] + 1)
		latestTime = max(latestTime + 2, curr)
		dync[x] = max(dync[x] + dist, latestTime)
	print(min(dync))


INF = 2 * 10 ** 9
for _ in range(int(input())):
	m = int(input())
	a = [[int(x) for x in input().split()] for i in range(2)]
	su = [[-INF for j in range(m + 1)] for i in range(2)]
	for i in range(2):
		for j in range(m - 1, -1, -1):
			su[i][j] = max(su[i][j + 1] - 1, a[i][j], a[i ^ 1][j] - (2 * (m - j) - 1))
	pr = a[0][0] - 1
	ans = INF
	for j in range(m):
		jj = j & 1
		ans = min(ans, max(pr, su[jj][j + 1] - 2 * j - 1, a[jj ^ 1][j] - 2 * m + 1))
		pr = max(pr, a[jj ^ 1][j] - 2 * j - 1)
		ans = min(ans, max(pr, su[jj ^ 1][j + 1] - 2 * j - 2))
		if j < m - 1:
			pr = max(pr, a[jj ^ 1][j + 1] - 2 * j - 2)
	print(ans + 2 * m)


INF = 2 * 10 ** 9
for _ in range(int(input())):
	(m, a) = (int(input()), [list(map(int, input().split())) for _ in range(2)])
	f = [[[-INF for _ in range(m + 1)] for _ in range(2)] for _ in range(2)]
	for i in range(m - 1, -1, -1):
		for j in range(2):
			f[j][0][i] = max(f[j][0][i + 1], a[j][i] + i)
			f[j][1][i] = max(f[j][1][i + 1], a[j][i] - i)
	a[0][0] = -1
	(s, ans) = (0, INF)
	for i in range(m):
		t = i & 1
		s = max(s, a[t][i] + 2 * (m - i))
		ans = min(ans, max(s, f[t ^ 1][0][i] - i + 1, f[t][1][i + 1] + 2 * m - i))
		s = max(s, a[t ^ 1][i] + 2 * (m - i) - 1)
	print(ans)


t = int(input())
for _ in range(t):
	m = int(input())
	r = [list(map(int, input().split())) for i in range(2)]
	r[0][0] = -1
	L = [0]
	R = [[[0], [0]], [[0], [0]]]
	for i in range(m):
		s = i & 1
		L.append(max(L[-1], 2 * (m - i) + max(r[0][i] - s, r[1][i] - 1 + s)))
		for j in range(2):
			for k in range(2):
				R[j][k].append(max(R[j][k][-1], r[j][-i - 1] + i * (2 * k - 1)))
	B = m + 1 + max(R[0][1][m], R[1][0][m] - 1)
	for i in range(1, m):
		s = i & 1
		B = min(B, max(L[i], m + 1 - i + max(R[0][1 - s][m - i] - s, R[1][s][m - i] - 1 + s)))
	print(B)