Welcome to ZOJ
 Contests Information Problems Runs Statistics Ranklist Clarification
148 - The 14th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple - M
Sequence to Sequence

Time Limit: 1 Second      Memory Limit: 65536 KB

Chiaki has a sequence s1, s2, ..., sn. She would like to change it to another sequence t1, t2, ..., tn using the following operations:

• choose two indices l and r (lr), and add 1 to every nonzero element between the indices l and r (both inclusive).
• choose two indices l and r (lr), 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.

#### Input

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 ≤ n ≤ 105) — the length of the sequence.

The second line contains n integers s1, s2, ..., sn (0 ≤ si ≤ 109).

The third line contains n integers t1, t2, ..., tn (0 ≤ ti ≤ 109).

It is guaranteed that the sum of n over all test cases does not exceed 106.

#### Output

For each test case, output an integer denoting the minimum number of operations. If it is impossible to change the sequence, output -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
```

#### Hint

For the first test case:

.

Submit    Status