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.