题目描述

Inna is an avid hiker. She's visiting a range of $n$ mountains with heights $h_1, h_2, \ldots, h_n$.

At a nearby shop, Inna has found a book that mentions that at some point in the past, the heights of the mountains were $p_1, p_2, \ldots, p_n$ in the same order. However, there is no evidence of how old this book is.

The book also describes a model of erosion that makes the mountains shorter year after year. Every year, based on the weather, a certain height threshold $x$ can be determined. Then, every mountain with the current height of at least $x$ decreases in height by exactly $1$. Different years can have different values of $x$.

Inna is curious how old the book actually is, and whether the described model is sound. Help her figure out the smallest number of years in which erosion could take the mountains from heights $p_1, p_2, \ldots, p_n$ to heights $h_1, h_2, \ldots, h_n$ in the same order, or determine that it is impossible under the given model.

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$, denoting the number of mountains ($1 \le n \le 10^5$).

The second line contains $n$ integers $h_1, h_2, \ldots, h_n$, denoting the current heights of the mountains ($1 \le h_i \le 10^6$).

The third line contains $n$ integers $p_1, p_2, \ldots, p_n$, denoting the heights of the mountains in the same order at some point in the past ($1 \le p_i \le 10^6$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

输出格式

For each test case, print the smallest number of years in which erosion could take the mountains from heights $p_1, p_2, \ldots, p_n$ to heights $h_1, h_2, \ldots, h_n$, or a single integer $-1$ if the described model is unsound.

4
4
3 2 4 2
5 3 6 2
1
10
100000
5
1 2 3 4 5
1 2 3 4 5
3
1 4 6
4 1 8

2
99990
0
-1

提示

In the first test case, the heights of the mountains could go from $(5, 3, 6, 2)$ to $(3, 2, 4, 2)$ in just two years:

• Suppose that in the first year, $x = 4$. After this year, the heights of the mountains are $(4, 3, 5, 2)$.
• Suppose that in the second year, $x = 3$. After this year, the heights of the mountains are $(3, 2, 4, 2)$.