Set To Max (Hard Version)
Contest: Codeforces Round 914 (Div. 2)
Difficulty rating: 1800
Tags: constructive algorithms, data structures, divide and conquer, greedy, implementation, sortings

This is the hard version of the problem. The only differences between the two versions of this problem are the constraints on $$$n$$$ and the time limit. You can make hacks only if all versions of the problem are solved.

You are given two arrays $$$a$$$ and $$$b$$$ of length $$$n$$$.

You can perform the following operation some (possibly zero) times:

1. choose $$$l$$$ and $$$r$$$ such that $$$1 \leq l \leq r \leq n$$$.
2. let $$$x=\max(a_l,a_{l+1},\ldots,a_r)$$$.
3. for all $$$l \leq i \leq r$$$, set $$$a_i := x$$$.

Determine if you can make array $$$a$$$ equal to array $$$b$$$.

Input format:
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the arrays.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the elements of array $$$a$$$.

The third line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$) — the elements of array $$$b$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output "YES" (without quotes) if you can make $$$a$$$ into $$$b$$$ using any number of operations, and "NO" (without quotes) otherwise.

You can output "YES" and "NO" in any case (for example, strings "yES", "yes" and "Yes" will be recognized as a positive response).

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
In the first test case, we can achieve array $$$b$$$ by applying a single operation: $$$(l,r)=(2,3)$$$.

In the second test case, it can be shown we cannot achieve array $$$b$$$ in any amount of operations.

In the third test case, we can achieve array $$$b$$$ by applying two operations: $$$(l,r)=(2,5)$$$. followed by $$$(l,r)=(1,3)$$$.

In the fourth and fifth test cases, it can be shown we cannot achieve array $$$b$$$ in any amount of operations.

Example input:
5
5
1 2 3 2 4
1 3 3 2 4
5
3 4 2 2 4
3 4 3 4 4
5
3 2 1 1 1
3 3 3 2 2
2
1 1
1 2
3
1 1 2
2 1 2

Example output:
YES
NO
YES
NO
NO

Editorial:
If $$$b_i < a_i$$$ for any $$$i$$$, then it is clearly impossible.
In order for $$$a_i$$$ to become $$$b_i$$$, $$$i$$$ must be contained by an interval that also contains a $$$j$$$ where $$$a_j = b_i$$$. Note that if there is a triple $$$i \le j < k$$$ where $$$a_j = a_k = b_i$$$, then it is never optimal to apply the operation on interval $$$[i, k]$$$, since applying the operation on interval $$$[i, j]$$$ will be sufficient. Thus, for $$$i$$$ we only need to consider the closest $$$a_j = b_i$$$ to the right or left of $$$i$$$.
Lets find the necessary conditions for us to apply an operation on the interval $$$[i, j]$$$. First of all, $$$a_k \le b_i$$$ for $$$i \le k \le j$$$. Second, $$$b_k \ge b_i$$$ for all $$$i \le k \le j$$$. Turns out, these conditions are also sufficient, since we can apply these operations in increasing order of $$$b_i$$$ without them interfering with each other. If we check for every $$$i$$$ there exists an interval $$$[i, j]$$$ or $$$[j, i]$$$ that satisfies the necessary conditions, then there will exist a sequence of operations to transform $$$a$$$ into $$$b$$$. Checking for the conditions can be done using monotonic stacks or segment trees.