You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

一条长廊上依次放置了 $n$ 个共振器。第 $i$ 个共振器当前的频率偏移量为 $a_i$，目标偏移量为 $b_i$。

调律装置只能从长廊的一端启动。一次操作中，你可以任选一个非零整数 $x$，并执行以下两种操作之一：

1. 选择一个 $k$（$1\le k\le n$），将前缀 $a_1,a_2,\ldots,a_k$ 中的每个数都加上 $x$；
2. 选择一个 $k$（$1\le k\le n$），将后缀 $a_k,a_{k+1},\ldots,a_n$ 中的每个数都加上 $x$。

$x$ 可以为正数或负数。无论 $|x|$ 多大，本次修改都只计为一次操作。

求将序列 $a$ 变为序列 $b$ 所需的最少操作次数。

输入格式

第一行一个整数 $T(1\le T\le 10^4)$，表示测试用例数量。

对于每个测试用例：

• 第一行一个整数 $n(1\le n\le 2\times 10^5)$；

• 第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n(-10^9 \le a_i \le 10^9)$；

• 第三行 $n$ 个整数 $b_1,b_2,\ldots,b_n(-10^9 \le b_i \le 10^9)$。

保证所有测试用例的 $n$ 之和不超过 $2\times10^5$，所有测试用例的 $\sum|a_i-a_{i-1}|(i \ge 2)$ 之和与 $\sum|b_i-b_{i-1}|(i \ge 2)$ 之和分别不超过 $10^4$。

输出格式

对于每个测试用例，输出一行一个整数，表示最少操作次数。

样例

4
3
0 0 0
-1 2 0
3
0 0 0
3 1 4
4
1 4 2 8
6 9 7 13
2
-7 10
-7 10

2
3
1
0

样例说明

对于第一个测试用例，可以执行：

1. 给长度为 $1$ 的前缀加上 $-3$，得到 $[-3,0,0]$；
2. 给长度为 $2$ 的前缀加上 $2$，得到 $[-1,2,0]$。

对于第三个测试用例，给整个序列加上 $5$ 即可。