Cutting Plants

All submissions for this problem are available.

Read problems statements in Mandarin chinese, Russian and Vietnamese as well.

Daniil is a royal gardener. He takes care of a garden with $N$ plants numbered $1$ through $N$. For each $i$ ($1 \le i \le N$), the initial height of the $i$-th plant is $A_i$. Unfortunately, the Queen doesn't like the garden, so she asked Daniil to cut some plants — in order to satisfy the Queen's request, the $i$-th plant should have height $B_i$ (for each $1 \le i \le N$). Daniil is allowed to perform the following operation an arbitrary number of times (including zero): - Let's denote the current heights of plants by $H_1, H_2, \dots, H_N$. - Choose two indices $L$ and $R$ ($1 \le L \le R \le N$) and a new height $h$ such that $h \le H_i$ for each $i$ between $L$ and $R$ inclusive. - Cut plants $L$ through $R$ down to height $h$, i.e. change the height of plant $i$ to $h$ for each $L \le i \le R$. Some time ago, Daniil was one of the best competitive programmers. Therefore, he is interested in the minimum number of operations needed to satisfy the Queen's request. Can you help him? ### Input - The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows. - The first line of each test case contains a single integer $N$ denoting the number of plants. - The second line contains $N$ space-separated integers $A_1, A_2, \dots, A_N$ denoting the initial heights of plants. - The third line contains $N$ space-separated integers $B_1, B_2, \dots, B_N$ denoting the final heights of plants. ### Output For each test case, print a single line containing one integer — the minimum number of operations needed to obtain the desired sequence of heights or $-1$ if it is impossible. ### Constraints - $1 \le T \le 10$ - $1 \le N \le 10^5$ - $1 \le A_i, B_i \le 10^9$ for each valid $i$ ### Subtasks **Subtask #1 (30 points):** - $1 \le N \le 1,000$ - the initial heights of all plants are identical **Subtask #2 (30 points):** $1 \le N \le 1,000$ **Subtask #3 (40 points):** original constraints ### Example Input

4
3
3 1 3
2 1 2
7
1 3 4 5 1 2 3
1 2 1 2 1 1 1
3
2 3 9
2 3 9
2
1 2
2 1

### Example Output

2
3
0
-1

### Explanation **Example case 1:** Daniil can perform two operations: reduce the height of the first plant to $2$ and reduce the height of the third plant to $2$. Note that it is not possible to reduce the heights of all three plants to $2$ in one operation, because the second plant's height is less than $2$. We need two operations, thus the answer is $2$. **Example case 2:** In the first operation, cut the plants in the interval $[2, 4]$ down to height $2$. Afterwards, cut the third plant down to height $1$. Finally, cut the plants in the interval $[6, 7]$. **Example case 3:** All plants already have the desired heights, so the answer is $0$. **Example case 4:** It is impossible to achieve the desired sequence of heights.