Description
You are given two sequences of positive integers \(a_1,\dots,a_n\) and \(b_1,\dots,b_n\).
Let \(h_1, h_2, \dots\) be an infinite array, initially all zero.
Let \(c\) be an empty sequence.
You may perform the following operations in any order and any number of times:
Operations
- OP1
If this is the \(k\)-th time OP1 is performed and \(k \le n\), increase $h_1, h_2, \dots, h_{a_k}$ by \(1\).
- OP2
If \(h_1 > 0\), let \(j\) be the largest index such that \(h_j = h_1\).
Decrease \(h_1,\dots,h_j\) by \(1\), and append \(j\) to \(c\).
- OP3
If \(h_1 > 0\), let \(j\) be the largest index such that \(h_j > 0\).
Decrease \(h_1,\dots,h_j\) by \(1\), and append \(j\) to \(c\).
Your task is to determine whether it is possible to obtain \(c = b\).
If it is possible, output Yes.
Otherwise, output No.
Constraints
- $1 \le t \le 1000$
- $1 \le n \le 5 \times 10^5$
- the sum of $n$ over all test cases $\le 10^5$
- $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 it is possible to obtain \(c = b\).No otherwise.
The output for each query should be followed by a newline (including the last one).
Tags