Это сложная версия задачи. Единственное различие между двумя версиями — это ограничение на \(n\) и ограничение по времени. Вы можете делать взломы, только если обе версии задачи решены.
Вам даны два массива \(a\) и \(b\) длины \(n\).
Вы можете выполнить следующую операцию несколько (возможно, ноль) раз:
- выбрать \(l\) и \(r\) такие, что \(1 \leq l \leq r \leq n\).
- пусть \(x=\max(a_l,a_{l+1},\ldots,a_r)\).
- для всех \(l \leq i \leq r\), присвоить \(a_i := x\).
Определите, можно ли сделать массив \(a\) равным массиву \(b\).
Выходные данные
Для каждого набора входных данных выведите «YES» (без кавычек), если вы можете превратить \(a\) в \(b\) с помощью данных операций, и «NO» (без кавычек) в противном случае.
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
Примечание
В первом наборе входных данных мы можем получить массив \(b\), применив единственную операцию: \((l,r)=(2,3)\).
Во втором наборе входных данных можно показать, что мы не можем получить массив \(b\) ни при каком количестве операций.
В третьем наборе входных данных массив \(b\) можно получить, применив две операции: \((l,r)=(2,5)\) и \((l,r)=(1,3)\).
В четвертом и пятом наборах входных данных можно показать, что массив \(b\) не может быть получен ни при каком количестве операций.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|