B'This is the hard version of the problem. The only difference between the versions is the constraints on n , k , a_i , and the sum of n over all test cases. You can make hacks only if both versions of the problem are solved. Note the unusual memory limit. You are given an array of integers a_1, a_2, ldots, a_n of length n , and an integer k . The cost of an array of integers p_1, p_2, ldots, p_n of length n is max limits_{1 <= i <= n} <= ft( <= ft lfloor frac{a_i}{p_i} right rfloor right) - min limits_{1 <= i <= n} <= ft( <= ft lfloor frac{a_i}{p_i} right rfloor right). Here, lfloor frac{x}{y} rfloor denotes the integer part of the division of x by y . Find the minimum cost of an array p such that 1 <= p_i <= k for all 1 <= i <= n . The first line contains a single integer t ( 1 <= t <= 100 ) -- the number of test cases. The first line of each test case contains two integers n and k ( 1 <= n, k <= 10^5 ). The second line contains n integers a_1, a_2, ldots, a_n ( 1 <= a_1 <= a_2 <= ldots <= a_n <= 10^5 ). It is guaranteed that the sum of n over all test cases does not exceed 10^5 . For each test case, print a single integer -- the minimum possible cost of an array p satisfying the condition above. In the first test case, the optimal array is p = [1, 1, 1, 2, 2] . The resulting array of values of lfloor frac{a_i}{p_i} rfloor is [4, 5, 6, 4, 5] . The cost of p is max limits_{1 <= i <= n}( lfloor frac{a_i}{p_i} rfloor) - min limits_{1 <= i <= n}( lfloor frac{a_i}{p_i} rfloor) = 6 - 4 = 2 . We can show that there is no array (satisfying the condition from the statement) with a smaller cost. In the second test case, one of the optimal arrays is p = [12, 12, 12, 12, 12] , which results in all lfloor frac{a_i}{p_i} rfloor be'...