D2. Присвоить максимум (сложная версия)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Единственное различие между двумя версиями — это ограничение на $$$n$$$ и ограничение по времени. Вы можете делать взломы, только если обе версии задачи решены.

Вам даны два массива $$$a$$$ и $$$b$$$ длины $$$n$$$.

Вы можете выполнить следующую операцию несколько (возможно, ноль) раз:

  1. выбрать $$$l$$$ и $$$r$$$ такие, что $$$1 \leq l \leq r \leq n$$$.
  2. пусть $$$x=\max(a_l,a_{l+1},\ldots,a_r)$$$.
  3. для всех $$$l \leq i \leq r$$$, присвоить $$$a_i := x$$$.

Определите, можно ли сделать массив $$$a$$$ равным массиву $$$b$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длину массивов.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — элементы массива $$$a$$$.

Третья строка содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$) — элементы массива $$$b$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите «YES» (без кавычек), если вы можете превратить $$$a$$$ в $$$b$$$ с помощью данных операций, и «NO» (без кавычек) в противном случае.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример
Входные данные
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
Выходные данные
YES
NO
YES
NO
NO
Примечание

В первом наборе входных данных мы можем получить массив $$$b$$$, применив единственную операцию: $$$(l,r)=(2,3)$$$.

Во втором наборе входных данных можно показать, что мы не можем получить массив $$$b$$$ ни при каком количестве операций.

В третьем наборе входных данных массив $$$b$$$ можно получить, применив две операции: $$$(l,r)=(2,5)$$$ и $$$(l,r)=(1,3)$$$.

В четвертом и пятом наборах входных данных можно показать, что массив $$$b$$$ не может быть получен ни при каком количестве операций.