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). 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.