B'This is the hard version of this problem. The difference between easy and hard versions is only the constraints on a_i and on n . You can make hacks only if both versions of the problem are solved. Burenka is the crown princess of Buryatia, and soon she will become the n -th queen of the country. There is an ancient tradition in Buryatia -- before the coronation, the ruler must show their strength to the inhabitants. To determine the strength of the n -th ruler, the inhabitants of the country give them an array of a of exactly n numbers, after which the ruler must turn all the elements of the array into zeros in the shortest time. The ruler can do the following two-step operation any number of times: Help Burenka calculate how much time she will need. The first line contains a single integer t (1 <= t <= 500) -- the number of test cases. The description of the test cases follows. The first line of each test case contains a single integer n (1 <= n <= 10^5) - the size of the array The second line of each test case contains n integers a_1, a_2, cdots , a_n (0 <= a_i < 2^{30}) -- elements of the array. It is guaranteed that the sum of n in all tests does not exceed 10^5 . For each test case, output a single number -- the minimum time that Burenka will need. In the first test case, Burenka can choose segment l = 1 , r = 4 , and x=5 . so it will fill the array with zeros in 2 seconds. In the second test case, Burenka first selects segment l = 1 , r = 2 , and x = 1 , after which a = [0, 2, 2] , and then the segment l = 2 , r = 3 , and x=2 , which fills the array with zeros. In total, Burenka will spend 2 seconds. '...