Description
You are given an integer $n$, and two arrays of length $n$:
- an array of positive integers $a_1, a_2, \dots, a_n$,
- an array of positive integers $b_1, b_2, \dots, b_n$.
You also have infinitely many rods, labeled by positive integers $1, 2, 3, \dots$ from left to right.
Each rod can hold beads stacked vertically.
At any moment, we use a non-negative integer $h_i$ to denote the current number of beads on rod $i$.
Initially, all rods are empty: $h_1 = h_2 = h_3 = \dots = 0$.
You are allowed to perform exactly $n$ operations of type 1 and exactly $n$ operations of type 2, in any interleaving order.
Operation 1 will consume the values of array $a$ from left to right (that is, the first type-1 operation uses $a_1$, the second uses $a_2$, and so on until $a_n$).
During the whole process, as a consequence of the rules below, the rod heights will always satisfy
$h_1 \ge h_2 \ge h_3 \ge \dots$.
You can perform two types of operations:
- Type 1: Place beads
Suppose this is the $k$-th type-1 operation.
Let $x = a_k$.
For every rod $i$ with $1 \le i \le x$, you drop one bead onto rod $i$.
Formally, $h_i \leftarrow h_i + 1$ for all $1 \le i \le x$.
For rods $i > x$, nothing changes.
Beads do not move sideways; each bead simply stays on the rod where it is dropped.
Since each type-1 operation always increases the heights of a prefix $1, 2, \dots, x$, and we start from all zeros, after any sequence of operations we always have $h_1 \ge h_2 \ge h_3 \ge \dots$ .
- Type 2: Remove beads
A type-2 operation may only be performed when at least one rod is non-empty, that is, when there exists some $i$ with $h_i > 0$.
Let $H = \max{h_i \mid i \ge 1}$.
Because the heights are always non-increasing from left to right, the rods whose height equals $H$ form a prefix ${1, 2, \dots, y}$ for some integer $y \ge 1$.
This operation removes one bead from each rod $1, 2, \dots, y$.
Formally, $h_i \leftarrow h_i - 1$ for all $1 \le i \le y$.
At the same time, you append the integer $y$ to an output sequence $c$.
If we perform type-2 operations exactly $n$ times, in some order, we obtain a sequence
$c_1, c_2, \dots, c_n$, where $c_k$ is the value produced by the $k$-th type-2 operation.
Your task is to determine whether there exists some interleaving of the $n$ type-1 operations and the $n$ type-2 operations, following all the rules above, such that the resulting sequence $c$ is exactly equal to the given sequence $b$; that is, $c_i = b_i$ for all $1 \le i \le n$.
If such an operation sequence exists, output Yes.
Otherwise, output No.
Constraints
- $1 \le t \le 1000$
- $1 \le n \le 5 \times 10^5$
- $\sum n \le 5 \times 10^5$ over all test cases
- $1 \le a_i \le 10^9$
- $1 \le b_i \le 10^9$
Subtasks
- Testcases 1, 2 : $n \le 100, 1 \le a_i,b_i \le 100$
- Testcases 3, 4 : $1 \le n \le 700$
- Testcases 5, 6 : No further constraints.
Input
The first line contains an integer $t$, the number of test cases.
Each test case consists of:
One line with an integer $n$.
One line with $n$ integers $a_1, a_2, \dots, a_n$.
One line with $n$ integers $b_1, b_2, \dots, b_n$.
$n$
$a_1$ $a_2$ ... $a_n$
$b_1$ $b_2$ ... $b_n$ |
Output
For each test case, print a single line:
Yes if there exists a valid sequence of operations that produces $b$.No otherwise.
The output for each query should be followed by a newline (including the last one).
Tags