You are given two arrays A and B, each of size N. You can perform the following types of operations on array A.

Type 1: Select any prefix of A and increment all its elements by 1.
Type 2: Select any suffix of A and increment all its elements by 1.

Your task is to transform the array A into array B using the minimum number of operations. If it is impossible to do so, output -1.

For an array A having N elements:
A prefix of the array A is a subarray starting at index 1.
A suffix of the array A is a subarray ending at index N.

------ Input Format ------ 

- First line will contain T, number of test cases. Then the test cases follow.
- The first line of each test case contains a single integer N, the size of arrays A and B.
- The next line contains N space-separated integers, where the i^{th} integer denotes A_{i}.
- The next line contains N space-separated integers, where the i^{th} integer denotes B_{i}.

------ Output Format ------ 

For each test case, print a single line containing one integer ―  minimum operations required to convert A into B. Print -1 if it is impossible to convert A into B.

------ Constraints ------ 

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 10^{5}$
$ -10^{14} ≤ A_{i}, B_{i} ≤ 10^{14} $
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
3
5
2 3 5 1 2
4 3 6 2 3
4
0 0 0 0
1 2 2 1
3
1 2 3
1 2 2
----- Sample Output 1 ------ 
3
2
-1
----- explanation 1 ------ 
Test Case $1$: Given $A = [2,3,5,1,2]$. It can be converted to array $B = [4, 3, 6, 2, 3]$ in $3$ operations:
- Operation $1$: Perform a type $1$ operation. Choose the prefix of length $1$ and increment the elements by $1$. Thus, the updated array is $A = [3, 3, 5, 1, 2]$.
-  Operation $2$: Perform a type $1$ operation. Choose the prefix of length $1$ and increment the elements by $1$. Thus, the updated array is $A = [4, 3, 5, 1, 2]$.
- Operation $3$: Perform a type $2$ operation. Choose the suffix of length $3$ and increment the elements by $1$. Thus, the updated array is $A = [4, 3, 6, 2, 3]$.

It can be proven that we cannot convert the array $A$ into array $B$ in less than $3$ operations.

Test Case $2$: Given $A = [0,0,0,0]$. It can be converted to array $B = [1,2,2,1]$ in $2$ operations:
- Operation $1$: Perform a type $1$ operation. Choose the prefix of length $3$ and increment the elements by $1$. Thus, the updated array is $A = [1,1,1,0]$.
-  Operation $2$: Perform a type $2$ operation. Choose the suffix of length $3$ and increment the elements by $1$. Thus, the updated array is $A = [1,2,2,1]$.

It can be proven that we cannot convert the array $A$ into array $B$ in less than $2$ operations.

Test Case $3$: Given $A = [1,2,3]$. The value of $A[3]$ will always be greater than $B[3]$. Hence, it is impossible to convert $A$ into $B$ using any number of operations.

Difficulty: VERY_HARD
Tags: Constructive algorithms

Starter code:

Solutions:
def presufop():
	for t in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		b = list(map(int, input().split()))
		(op1, op2) = (b[0] - a[0], 0)
		(res1, res2) = (0, 0)
		for i in range(n):
			if op1 + op2 < b[i] - a[i]:
				op2 += b[i] - a[i] - op1 - op2
			elif op1 + op2 > b[i] - a[i]:
				op1 -= op1 + op2 - (b[i] - a[i])
			if op1 < 0 or op2 > b[n - 1] - a[n - 1]:
				res1 = -1
				res2 = 0
				break
			res1 = max(res1, op1)
			res2 = max(res2, op2)
		print(res1 + res2)
presufop()


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	if a == b:
		print(0)
	elif any((a[i] > b[i] for i in range(n))):
		print(-1)
	else:
		(ans, suff_sum, pref_add) = (0, 0, 0)
		for i in range(n):
			if i == 0:
				ans += b[0] - a[0]
				pref_add = ans
			else:
				diff = b[i] - a[i] - suff_sum
				if diff < 0:
					ans = -1
					break
				if diff >= pref_add:
					suff_sum += diff - pref_add
				else:
					pref_add = diff
			if i == n - 1:
				ans += suff_sum
		print(ans)


from sys import stdin, stdout
from collections import Counter, defaultdict, deque
from math import sqrt, factorial, ceil
import heapq
inf = float('inf')
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	poss = True
	diff = [0 for j in range(n)]
	for j in range(n):
		if a[j] > b[j]:
			poss = False
			break
		else:
			diff[j] = b[j] - a[j]
	if poss:
		ans = 0
		leftsum = diff[0]
		rightsum = 0
		prevval = diff[0]
		for j in diff:
			cval = j - rightsum
			if cval < 0:
				ans = -1
				break
			elif cval < prevval:
				prevval = cval
			cright = cval - prevval
			rightsum += cright
			ans += cright
		if ans == -1:
			leftsum = 0
		print(ans + leftsum)
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	f = b[0] - a[0]
	s = 0
	x = y = 0
	for i in range(n):
		if f + s < b[i] - a[i]:
			s += b[i] - a[i] - f - s
		elif f + s > b[i] - a[i]:
			f -= f + s - (b[i] - a[i])
		if f < 0 or s > b[n - 1] - a[n - 1]:
			x = -1
			y = 0
			break
		x = max(x, f)
		y = max(y, s)
	print(x + y)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	aa = b[0] - a[0]
	bb = 0
	ans1 = 0
	ans2 = 0
	for i in range(n):
		if aa + bb < b[i] - a[i]:
			bb += b[i] - a[i] - aa - bb
		elif aa + bb > b[i] - a[i]:
			aa -= aa + bb - (b[i] - a[i])
		if aa < 0 or bb > b[n - 1] - a[n - 1]:
			ans1 = -1
			ans2 = 0
			break
		ans1 = max(ans1, aa)
		ans2 = max(ans2, bb)
	ans = ans1 + ans2
	print(ans)


for _ in range(int(input())):
	n = int(input())
	ans = 0
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a = [b[i] - a[i] for i in range(n)]
	for i in range(n - 1):
		if a[i + 1] < a[i]:
			ans += a[i] - a[i + 1]
	if ans > a[0]:
		print(-1)
		continue
	an = 0
	for i in range(1, n):
		if a[i] < a[i - 1]:
			an += abs(a[i] - a[i - 1])
	an += a[-1]
	print(an)


from math import ceil, gcd, factorial, sqrt, log, log2
import queue
from itertools import permutations, combinations, accumulate, product
from collections import Counter, deque
from sys import stdin, stdout
from bisect import bisect, insort, bisect_left, insort_left
input = stdin.readline

def sieve(n):
	prime = [True] * (n + 1)
	p = 2
	prime[0] = False
	prime[1] = False
	for p in range(2, int(n ** 0.5) + 1):
		if prime[p] == True:
			for l1 in range(p * p, n + 1, p):
				prime[l1] = False
	return prime

def simplesieve(n):
	prime = [2]
	mak = [False] * (n + 1)
	for p in range(3, n + 1, 2):
		if mak[p] == False:
			prime.append(p)
			if p * p <= n:
				for l1 in range(p * p, n + 1, 2 * p):
					mak[l1] = True
	return prime

def segementedsieve(low, high):
	primes = simplesieve(int(high ** 0.5))
	prime = [True] * (high - low + 1)
	for i in primes:
		lower = low // i * i
		if lower < low:
			lower += i
		for j in range(lower, high + 1, i):
			if j != i:
				prime[j - low] = False
	ans = []
	for i in range(low, high + 1):
		if prime[i - low]:
			ans.append(i)
	return ans

def isprime(n):
	if n == 2:
		return True
	if n % 2 == 0 or n == 1:
		return False
	for l1 in range(3, int(n ** 0.5) + 1, 2):
		if n % l1 == 0:
			return False
	return True

def binpow(a, b, m):
	r2 = 1
	a = a % m
	while b > 0:
		if b & 1:
			r2 = r2 * a % m
		a = a * a % m
		b >>= 1
	return r2

def lcm(a, b):
	return a // gcd(a, b) * b

def gcdExtended(a, b):
	if b == 0:
		return (a, 1, 0)
	(g, x1, y1) = gcdExtended(b, a % b)
	(x1, y1) = (y1, x1 - a // b * y1)
	return (g, x1, y1)

def binseach(a, l, r, key):
	while r - l > 1:
		m = l + (r - l) // 2
		if a[m] <= key:
			l = m
		else:
			r = m
	if a[l] == key:
		return l
	if a[r] == key:
		return r
	return -1

class Node:

	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None

def inorder(root):
	(res, stack) = ([], [])
	current = root
	while True:
		while current:
			stack.append(current)
			current = current.left
		if len(stack) == 0:
			return res
		node = stack[-1]
		stack.pop(len(stack) - 1)
		if node.data != None:
			res.append(node.data)
		current = node.right
	return res

def dfs(graph, s, v, ans):
	v[s] = 1
	ans.append(s)
	for i in graph[s]:
		if v[i] == 0:
			dfs(graph, i, v, ans)

def bfs(graph, n, x, dest):
	v = [0] * (1 + n)
	d = [0] * (1 + n)
	d[x] = 0
	v[x] = 1
	q = queue.Queue()
	q.put(x)
	while not q.empty():
		z = q.get()
		for s in graph[z]:
			if v[s] == 0:
				v[s] = 1
				d[s] = d[z] + 1
				q.put(s)
	return d[dest]
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	k = b[0] - a[0]
	c = 0
	r1 = r2 = 0
	for i in range(n):
		if k + c < b[i] - a[i]:
			c = b[i] - a[i] - k
		elif k + c > b[i] - a[i]:
			k -= k + c - (b[i] - a[i])
		if k < 0 or c > b[n - 1] - a[n - 1]:
			r1 = -1
			r2 = 0
			break
		r1 = max(r1, k)
		r2 = max(r2, c)
	print(r1 + r2)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ans1 = b[0] - a[0]
	ans2 = 0
	rem1 = rem2 = 0
	for i in range(n):
		if ans1 + ans2 < b[i] - a[i]:
			ans2 += b[i] - a[i] - ans1 - ans2
		elif ans1 + ans2 > b[i] - a[i]:
			ans1 -= ans1 + ans2 - (b[i] - a[i])
		if ans1 < 0 or ans2 > b[-1] - a[-1]:
			rem1 = -1
			rem2 = 0
			break
		rem1 = max(rem1, ans1)
		rem2 = max(rem2, ans2)
	out = rem1 + rem2
	print(out)


def findForSlope(A):
	ret = [0]
	for i in range(len(A) - 1):
		ret.append(A[i + 1] - A[i])
	return ret
t = int(input())
for _ in range(t):
	n = int(input())
	A = [int(x) for x in input().split()]
	B = [int(x) for x in input().split()]
	sB = findForSlope(B)
	sA = findForSlope(A)
	rn = []
	imp = False
	for i in range(n):
		diff = B[i] - A[i]
		if diff < 0:
			imp = True
		rn.append(diff)
	if imp:
		print('-1')
		continue
	if n == 1:
		print(rn[0])
		continue
	minranr = [0] * n
	minranr[n - 1] = rn[n - 1]
	minranl = [0] * n
	minranl[0] = rn[0]
	for i in range(1, n, 1):
		minranl[i] = min(rn[i], minranl[i - 1])
	for i in range(n - 2, -1, -1):
		minranr[i] = min(rn[i], minranr[i + 1])
	smA = sum(A)
	smB = sum(B)
	smadd = 0
	ans = 0
	lf = 10 ** 20
	rf = 0
	for i in range(n):
		diff = sB[i] - sA[i]
		if diff < 0:
			lff = min(lf, minranl[i - 1])
			if lff < abs(diff):
				imp = True
				break
			ans += abs(diff)
			smadd += abs(diff) * i
			lf = lff - abs(diff)
		if diff > 0:
			rff = minranr[i] - rf
			if rff < diff:
				imp = True
				break
			ans += diff
			rf = rf + abs(diff)
			smadd += diff * (n - i)
	if imp:
		print('-1')
		continue
	ans += int((smB - smA - smadd) / n)
	print(ans)


from bisect import bisect_left
import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():
	n = inp()
	a = li()
	b = li()
	mi = INF
	diff = [b[i] - a[i] for i in range(n)]
	for i in range(n):
		if diff[i] < 0:
			pr(-1)
			return
		if i:
			if diff[i - 1] > diff[i]:
				pr(-1)
				return
			mi = min(mi, diff[i] - diff[i - 1])
		else:
			mi = min(mi, diff[i])
		diff[i] -= mi
	pr(b[0] - a[0] + diff[-1])
for _ in range(inp()):
	solve()