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

Input

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

Output

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.

Note

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.

Vessels, Heights and Two Versions (Hard Version)

Examples