Это сложная версия задачи. Разница между версиями заключается в том, что в этой версии второй тест имеет $$$n=300\,000$$$. Взломы не допускаются в этой задаче.
Назовем последовательность целых чисел $$$a_1, a_2, \ldots, a_n$$$ выпуклой по расстоянию, если $$$|a_{i} - a_{i-1}| \lt |a_{i+1} - a_{i}|$$$ для каждого $$$1 \lt i \lt n$$$. Другими словами, если вы прыгаете по точкам $$$a_1, a_2, \ldots, a_n$$$ в этом порядке, каждый следующий прыжок строго длиннее предыдущего.
Вам даны два целых числа $$$n$$$ и $$$m$$$. Найдите выпуклую по расстоянию последовательность $$$a$$$ длины $$$n$$$, которая содержит не более $$$m$$$ различных значений. С точки зрения последовательности прыжков это означает, что вам нужно сделать $$$(n-1)$$$ прыжок увеличивающихся длин, посетив при этом не более $$$m$$$ различных точек. Для всех $$$1 \le i \le n$$$ должно выполняться $$$-10^{18} \le a_i \le 10^{18}$$$.
Входные данные состоят из двух целых чисел $$$n$$$ и $$$m$$$.
Для этой задачи есть только 2 теста.
Взломы не допускаются в этой задаче.
Выведите выпуклую по расстоянию последовательность $$$a_1, a_2, \ldots, a_n$$$, которая содержит не более $$$m$$$ различных значений. Для всех $$$1 \le i \le n$$$ должно выполняться $$$-10^{18} \le a_i \le 10^{18}$$$.
Если существует несколько решений, выведите любое из них.
8 6
1 1 3 6 10 3 11 1
Последовательность $$$[1, 1, 3, 6, 10, 3, 11, 1]$$$ имеет длину $$$n=8$$$ и содержит $$$5$$$ различных значений, что меньше или равно $$$m=6$$$. Разности между последовательными значениями равны $$$0,2,3,4,7,8,10$$$, что является строго возрастающей последовательностью.
$$$[1, 1, 2, 4, 8, 16, 32, 1]$$$ является еще одним допустимым ответом.
