#P14112. [ZJCPC 2017] Sequence to Sequence

[ZJCPC 2017] Sequence to Sequence

题目描述

Chiaki has a sequence s1,s2,,sns_1,s_2, \dots, s_n. She would like to change it to another sequence t1,t2,,tnt_1, t_2, \dots, t_n using the following operations:

  • choose two indices ll and rr (lrl \le r), and add 11 to every nonzero element between the indices ll and rr (both inclusive).
  • choose two indices ll and rr (lrl \le r), and subtract 11 from every nonzero element between the indices ll and rr (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 TT, indicating the number of test cases. For each test case:

The first line contains an integer nn (1n1051 \le n \le 10^5) -- the length of the sequence.

The second line contains nn integers s1,s2,,sns_1,s_2,\dots,s_n (0si1090 \le s_i \le 10^9).

The third line contains nn integers t1,t2,,tnt_1,t_2,\dots,t_n (0ti1090 \le t_i \le 10^9).

It is guaranteed that the sum of nn over all test cases does not exceed 10610^6.

输出格式

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

2
5
1 1 1 1 1
2 0 2 0 2
7
3 1 2 3 2 1 4
2 0 0 0 0 0 2
3
3

提示

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\}$.