山脊封锁
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 512 M,其他语言1024 M
64bit IO Format: %lld

题目描述

在一条漫长的山脉上,共设有 N 个观测点,第 i 个观测点当前的海拔高度为 a_i
为了维持整条山脉的地貌稳定,地质部门规定了一条特殊规则:
- 当前整条山脉中海拔最高的观测点,禁止继续抬高,即禁止使海拔最高的观测点的海拔上升 1
- 当前整条山脉中海拔最低的观测点,禁止继续降低,即禁止使海拔最低的观测点的海拔下降 1
- 除此之外,每次施工可以使某一个观测点的海拔上升 1,或下降 1
现在,勘测队希望将整条山脉的海拔分布从初始状态 A 调整为目标状态 B。请你判断这一目标能否实现;若能,求出所需的最少施工次数。
形式化的,给定两个长度均为 N 的整数序列 A=(a_1,a_2,\dots,a_N)B=(b_1,b_2,\dots,b_N)
你可以对序列 A 重复执行以下两种操作之一:
1. 选择一个下标 i\in \{1,2,\cdots,N\},若 a_i 不是当前序列中的最大值,则可以令 a_i\leftarrow a_i+1
2. 选择一个下标 i\in \{1,2,\cdots,N\},若 a_i 不是当前序列中的最小值,则可以令 a_i\leftarrow a_i-1
其中,当前序列中的最大值或最小值均指执行该次操作之前,序列 A 中所有元素的最大值或最小值。可以有多个最大值或最小值,这些最大值均不允许执行操作 1,最小值均不允许执行操作 2
请你求出将初始序列 A 变为目标序列 B 所需的最少操作次数。若无法变为目标序列,则输出 -1

输入描述:

第一行一个整数 T (1\leq T\leq 10^4),表示数据组数。
对于每组数据,第一行一个整数 N (1\leq N\leq 4\times 10^5),表示观测点数量。
第二行 N 个整数 a_1,a_2,\cdots,a_N (-10^9\leq a_i\leq 10^9),表示初始状态。
第三行 N 个整数 b_1,b_2,\cdots,b_N (-10^9\leq b_i\leq 10^9),表示目标状态。
保证单个测试点内所有数据中 N 的和不超过 2\times 10^6

输出描述:

对于每组数据,输出一行一个整数,表示最少操作次数;若无法变为目标序列,则输出 -1
示例1

输入

复制
6
3
1 3 2
2 2 1
4
2 5 3 4
2 6 3 4
3
7 7 7
7 7 6
2
0 1
1 0
2
0 5
3 3
1
10
8

输出

复制
3
-1
-1
-1
5
-1