{"extraResources":{"example.01.mu":"TVXzATQNCiFjMTs0DQozIDIgNCAyDQo1IDMgNiAyDQohYzI7MQ0KMTANCjEwMDAwMA0KIWMzOzUNCjEgMiAzIDQgNQ0KMSAyIDMgNCA1DQohYzQ7Mw0KMSA0IDYNCjQgMSA4DQo="},"scoring":null,"notes":"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:\r\n\\begin{itemize}\r\n\\item Suppose that in the first year, $x = 4$. After this year, the heights of the mountains are $(4, 3, 5, 2)$.\r\n\\item Suppose that in the second year, $x = 3$. After this year, the heights of the mountains are $(3, 2, 4, 2)$.\r\n\\end{itemize}","legend":"Inna is an avid hiker. She's visiting a range of $n$ mountains with heights $h_1, h_2, \\ldots, h_n$.\r\n\r\nAt 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.\r\n\r\nThe 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$.\r\n\r\nInna 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.","authorLogin":"tourist","language":"english","timeLimit":2000,"output":"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.","inputFile":"stdin","outputFile":"stdout","input":"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.\r\n\r\nThe first line of each test case contains a single integer $n$, denoting the number of mountains ($1 \\le n \\le 10^5$).\r\n\r\nThe 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$).\r\n\r\nThe 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$).\r\n\r\nIt is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.","authorName":"Gennady Korotkevich","sampleTests":[{"output":"2\r\n99990\r\n0\r\n-1\r\n","input":"4\r\n4\r\n3 2 4 2\r\n5 3 6 2\r\n1\r\n10\r\n100000\r\n5\r\n1 2 3 4 5\r\n1 2 3 4 5\r\n3\r\n1 4 6\r\n4 1 8\r\n","inputFile":"example.01","outputFile":"example.01.a"}],"name":"If I Could Turn Back Time","interaction":null,"memoryLimit":1073741824,"tutorial":"{\r\n    \\parindent=1cm\r\n    \\begin{tabular}{l@{\\extracolsep{1cm}}l}\r\n         Идея: & Георгий Корнеев\\\\\r\n         Разработка: & Геннадий Короткевич\\\\\r\n     \\end{tabular}\r\n}\r\n\r\nПоскольку порядок гор не имеет значения, переставим их по неубыванию текущей высоты (а при равенстве~--- по неубыванию старой высоты), то есть теперь, не умаляя общности, будем считать, что $h_1 \\le h_2 \\le \\ldots \\le h_n$.\r\n\r\nЗаметим, что все преобразования высот гор монотонны~--- а именно, если гора $A$ раньше была выше горы $B$, то она никаким образом не может стать ниже горы $B$ в результате эрозии. Значит, нужно проверить, что выполнено условие $p_1 \\le p_2 \\le \\ldots \\le p_n$, в противном случае можно вывести $-1$ и перейти к следующему тесту.\r\n\r\nПусть снова гора $A$ выше горы $B$. Тогда, если в каком-то году гора $B$ оказалась подвержена эрозии и уменьшилась в высоте, то гора $A$ тоже должна была быть ей подвержена (а обратное~--- не всегда верно). Значит, чем выше гора, тем сильнее она должна уменьшиться в размере. Формально, это условие можно записать как $p_1 - h_1 \\le p_2 - h_2 \\le \\ldots \\le p_n - h_n$~--- если условие не выполнено, можно также вывести $-1$.\r\n\r\nНаконец, если условия выше выполнены, можно показать, что всегда можно найти такую последовательность действий, которая приведёт высоты $p_1, p_2, \\ldots, p_n$ в высоты $h_1, h_2, \\ldots, h_n$. Поскольку любое действие, влияющее на горы, всегда уменьшает самую высокую гору, минимальное число таких действий (лет) равно $p_n - h_n$~--- это и будет ответом на задачу."}