Это сложная версия задачи. В этой версии \(m \leq 2\cdot 10^5\).
Скибидус получил два массива \(a\) и \(b\), содержащие соответственно \(n\) и \(m\) элементов. Для каждого целого числа \(i\) от \(1\) до \(n\) ему разрешено выполнить операцию не более одного раза:
- Выбрать целое число \(j\) такое, что \(1 \leq j \leq m\). Присвоить \(a_i := b_j - a_i\). Обратите внимание, что в результате этой операции \(a_i\) может стать неположительным.
Скибидус нуждается в вашей помощи, чтобы определить, может ли он отсортировать \(a\) в неубывающем порядке\(^{\text{∗}}\) выполнив вышеуказанную операцию некоторое количество раз.
Выходные данные
Для каждого набора входных данных, если возможно отсортировать \(a\) в неубывающем порядке, выведите «YES» на новой строке. В противном случае выведите «NO» на новой строке.
Вы можете выводить ответ в любом регистре. Например, строки «yEs», «yes», и «Yes» также будут распознаны как положительные ответы.
Примечание
В первом наборе входных данных \([5]\) уже отсортирован.
Во втором наборе входных данных можно показать, что это невозможно.
В третьем наборе входных данных мы можем установить \(a_2:=b_1-a_2=6-4=2\) и \(a_3:=b_3-a_3=8-6=2\). Последовательность \([2,2,2,5]\) отсортирована в неубывающем порядке.
В последнем случае мы можем применить операции на каждом индексе. Последовательность становится \([-1,0,1]\), которая отсортирована в неубывающем порядке.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 3
5
9 1 1000000000
3 2
1 4 3
3 4
4 3
2 4 6 5
6 1 8
5 2
6 4 5 4 5
4 1000
3 1
9 8 7
8
|
YES
NO
YES
NO
YES
|