CF2234F Vessels, Heights and Two Versions (Hard Version)

This is the hard version of the problem. The difference between the versions is that in this version, constraints on $ n $ and on the number of test cases are higher. You can hack only if you solved all versions of this problem. There are $ n $ communicating vessels of infinite height arranged in a circle. The base area of each vessel is $ 1 $ cm $ ^2 $ , and between the $ i $ -th vessel and the $ (i \bmod n) + 1 $ -th vessel there is a connection of negligible volume at height $ h_i $ cm. For each vessel $ i $ , find the maximum total volume of water in cm $ ^3 $ that can be placed in these vessels under the condition that the $ i $ -th vessel remains empty. Formally, you are given an array $ h_1, h_2, \ldots, h_n $ . A cyclic array of non-negative integers $ w_1, w_2, \ldots, w_n $ is called good if the following holds: - For every $ i $ from $ 1 $ to $ n $ , if $ \max(w_i, w_{i \bmod n + 1}) \gt h_i $ , then $ w_i = w_{i \bmod n + 1} $ . In other words, if the maximum of two neighboring elements of the array $ w $ exceeds the corresponding element of the array $ h $ , then these two neighboring elements of the array $ w $ must be equal. For each $ i $ from $ 1 $ to $ n $ , output the maximum possible sum $ w_1 + w_2 + \ldots + w_n $ among all good arrays $ w_1, w_2, \ldots, w_n $ , under the condition that $ w_i = 0 $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains one integer $ n $ ( $ 3 \le n \le 2 \cdot 10^5 $ ) — the number of vessels. The second line of each test case contains $ n $ integers $ h_1, h_2, \ldots, h_n $ ( $ 1 \le h_i \le 10^9 $ ) — the heights of the partitions between the vessels. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, output $ n $ integers — the $ l $ -th integer means the maximum total volume of water in cm $ ^3 $ in the vessels under the condition that the $ l $ -th vessel remains empty.

Consider the first test case. - To keep vessel $ 1 $ empty, one good array is $ w = [0, 1, 2, 3] $ , with a total of $ 6 $ cm $ ^3 $ of water. - To keep vessel $ 2 $ empty, one good array is $ w = [1, 0, 2, 3] $ , with a total of $ 6 $ cm $ ^3 $ of water. - To keep vessel $ 3 $ empty, one good array is $ w = [2, 2, 0, 3] $ , with a total of $ 7 $ cm $ ^3 $ of water. - To keep vessel $ 4 $ empty, one good array is $ w = [3, 3, 3, 0] $ , with a total of $ 9 $ cm $ ^3 $ of water. For example, the array $ w = [2, 2, 0, 4] $ is not good, because $ \max(w_3, w_4) \gt h_3 $ , and therefore $ w_3 = w_4 $ must hold. It can be shown that each of the arrays above has the maximum possible sum among all suitable options.