If I Could Turn Back Time

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

At a nearby shop, Inna found a book stating that at some point in the past, the mountains had heights $p_1, p_2, \ldots, p_n$, in the same order. The book does not say how old it is.

The book also describes an erosion model that makes the mountains shorter year after year. Each year, the weather sets a height threshold $x$. Every mountain whose current height is at least $x$ decreases by exactly $1$. Different years can use different values of $x$.

Inna wants to know how old the book is and whether the model is sound. Find the smallest number of years in which erosion could take the mountains from heights $p_1, \ldots, p_n$ to heights $h_1, \ldots, h_n$, in the same order, or determine that the model cannot do this.

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

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

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

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

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 $p_1, \ldots, p_n$ to $h_1, \ldots, h_n$. If the model is unsound, print $-1$ instead.

In the first test case, the heights can go from $(5, 3, 6, 2)$ to $(3, 2, 4, 2)$ in just two years.

• In the first year, let $x = 4$. Afterward, the heights are $(4, 3, 5, 2)$.
• In the second year, let $x = 3$. Afterward, the heights are $(3, 2, 4, 2)$.