题号:NC318521
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 512 M,其他语言1024 M
64bit IO Format: %lld
题目描述
在一条漫长的山脉上,共设有

个观测点,第

个观测点当前的海拔高度为

。
为了维持整条山脉的地貌稳定,地质部门规定了一条特殊规则:
- 当前整条山脉中海拔最高的观测点,禁止继续抬高,即禁止使海拔最高的观测点的海拔上升

;
- 当前整条山脉中海拔最低的观测点,禁止继续降低,即禁止使海拔最低的观测点的海拔下降

;
- 除此之外,每次施工可以使某一个观测点的海拔上升

,或下降

。
现在,勘测队希望将整条山脉的海拔分布从初始状态

调整为目标状态

。请你判断这一目标能否实现;若能,求出所需的最少施工次数。
形式化的,给定两个长度均为

的整数序列
)
和
)
。
你可以对序列

重复执行以下两种操作之一:
1. 选择一个下标

,若

不是当前序列中的最大值,则可以令

;
2. 选择一个下标

,若

不是当前序列中的最小值,则可以令

。
其中,当前序列中的最大值或最小值均指执行该次操作之前,序列

中所有元素的最大值或最小值。可以有多个最大值或最小值,这些最大值均不允许执行操作

,最小值均不允许执行操作

。
请你求出将初始序列

变为目标序列

所需的最少操作次数。若无法变为目标序列,则输出

。
输入描述:
第一行一个整数
,表示数据组数。
对于每组数据,第一行一个整数
,表示观测点数量。
第二行
个整数
,表示初始状态。
第三行
个整数
,表示目标状态。
保证单个测试点内所有数据中
的和不超过
。
输出描述:
对于每组数据,输出一行一个整数,表示最少操作次数;若无法变为目标序列,则输出
。
示例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