CF2147I2 Longest Increasing Path (Hard Version)

This is the hard version of the problem. The difference between the versions is that in this version the second test is $ n=300\,000 $ . Hacks are not allowed in this problem. Let's call an integer sequence $ a_1, a_2, \ldots, a_n $ distance-convex if $ |a_{i} - a_{i-1}| < |a_{i+1} - a_{i}| $ for every $ 1 < i < n $ . In other words, if you jump through the points $ a_1, a_2, \ldots, a_n $ in this order, each next jump is strictly longer than the previous one. You are given two integers $ n $ and $ m $ . Find a distance-convex sequence $ a $ of length $ n $ that contains at most $ m $ distinct values. In terms of the jump sequence, that would mean that you need to make $ (n-1) $ jumps of increasing lengths while visiting at most $ m $ distinct points. $ -10^{18} \le a_i \le 10^{18} $ should hold for all $ 1 \le i \le n $ .

Input consists of two integers $ n $ and $ m $ . There are only 2 tests for this problem. - $ n = 8 $ , $ m = 6 $ ; - $ n = 300\,000 $ , $ m = 15\,000 $ . It is guaranteed that an answer exists for both tests.Hacks are not allowed in this problem.

Print a distance-convex sequence $ a_1, a_2, \ldots, a_n $ that contains at most $ m $ distinct values. $ -10^{18} \le a_i \le 10^{18} $ should hold for all $ 1 \le i \le n $ . If there are multiple solutions, print any of them.

The sequence $ [1, 1, 3, 6, 10, 3, 11, 1] $ has length $ n=8 $ and contains $ 5 $ different values, which is less than or equal to $ m=6 $ . The differences between consecutive values are $ 0,2,3,4,7,8,10 $ , a strictly increasing sequence. $ [1, 1, 2, 4, 8, 16, 32, 1] $ would be another valid answer.