P14112 [ZJCPC 2017] Sequence to Sequence

Chiaki has a sequence $s_1,s_2, \dots, s_n$. She would like to change it to another sequence $t_1, t_2, \dots, t_n$ using the following operations: - choose two indices $l$ and $r$ ($l \le r$), and add $1$ to every nonzero element between the indices $l$ and $r$ (both inclusive). - choose two indices $l$ and $r$ ($l \le r$), and subtract $1$ from every nonzero element between the indices $l$ and $r$ (both inclusive). Chiaki would like to know the minimum number of operations needed.

There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case: The first line contains an integer $n$ ($1 \le n \le 10^5$) -- the length of the sequence. The second line contains $n$ integers $s_1,s_2,\dots,s_n$ ($0 \le s_i \le 10^9$). The third line contains $n$ integers $t_1,t_2,\dots,t_n$ ($0 \le t_i \le 10^9$). It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

For each test case, output an integer denoting the minimum number of operations. If it is impossible to change the sequence, output $-1$ instead.

For the first test case: $\{1,1,1,1,1\} \xrightarrow{[2,2],\ -1} \{1,0,1,1,1\} \xrightarrow{[4,4],\ -1} \{1,0,1,0,1\} \xrightarrow{[1,5],\ +1} \{2, 0, 2, 0, 2\}$.