B"This is the hard version of the problem. The only difference between the versions is the constraints on a_i . You can make hacks only if both versions of the problem are solved. Nene is fighting with n monsters, located in a circle. These monsters are numbered from 1 to n , and the i -th ( 1 <= i <= n ) monster's current energy level is a_i . Since the monsters are too strong, Nene decided to fight with them using the Attack Your Neighbour spell. When Nene uses this spell, the following actions happen in the following order one by one: When the monster with energy level x attacks the monster with the energy level y , the energy level of the defending monster becomes max(0, y-x) (the energy level of the attacking monster remains equal to x ). Nene is going to use this spell 10^{100} times and deal with the monsters that will still have a non-zero energy level herself. She wants you to determine which monsters will have a non-zero energy level once she will use the described spell 10^{100} times. Each test contains multiple test cases. The first line contains the number of test cases t ( 1 <= t <= 10^4 ). The description of test cases follows. The first line contains a single integer n ( 2 <= n <= 2 cdot 10^5 ) -- the number of monsters. The second line contains n integers a_1, a_2, ldots, a_n ( 0 <= a_i <= 10^9 ) -- the current energy levels of monsters. It is guaranteed that the sum of n over all test cases does not exceed 2 cdot 10^5 . For each test case, If m=0 , you may either output an empty line or don't output it. In the first test case, the following actions happen during the first 3 uses of the spell in this order: After each of the next uses of the spell, energy levels of monsters do not change. Thus, only the 1 -st monster has a non-zero energy level in the end. In the second test case, both monste"...