F. Сосуды, высоты, две версии (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии ограничения на $$$n$$$ и на количество наборов входных данных меньше. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

По кругу стоят $$$n$$$ сообщающихся сосудов бесконечной высоты, площадь основания каждого из сосудов равна $$$1$$$ см$$$^2$$$, между $$$i$$$-м и $$$(i \bmod n) + 1$$$-м есть соединение пренебрежимо малого объёма на высоте $$$h_i$$$ см. Для каждого сосуда $$$i$$$ найдите, какой наибольший суммарный объём воды в см$$$^3$$$ можно уместить в этих сосудах при условии, что $$$i$$$-й сосуд останется пустым.

Формально, вам дан массив $$$h_1, h_2, \ldots, h_n$$$. Назовём циклический массив целых неотрицательных чисел $$$w_1, w_2, \ldots, w_n$$$ хорошим, если выполняется:

  • Для каждого $$$i$$$ от $$$1$$$ до $$$n$$$, для которого выполняется $$$\max(w_i, w_{i \bmod n + 1}) \gt h_i$$$, также выполняется $$$w_i = w_{i \bmod n + 1}$$$. То есть, если максимум двух соседних элементов массива $$$w$$$ превосходит соответствующий элемент массива $$$h$$$, то эти два соседних элемента массива $$$w$$$ должны быть равны.

Требуется для каждого $$$i$$$ от $$$1$$$ до $$$n$$$ сообщить максимальную сумму $$$w_1 + w_2 + \ldots + w_n$$$ среди всех хороших массивов $$$w_1, w_2, \ldots, w_n$$$, при условии, что $$$w_i = 0$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных содержится одно число $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — количество сосудов.

Во второй строке каждого набора входных данных содержится $$$n$$$ целых чисел $$$h_1, h_2, \ldots, h_n$$$ ($$$1 \le h_i \le 10^9$$$) — высоты перегородок между сосудами.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$n$$$ целых чисел — $$$l$$$-е число означает наибольший суммарный объём воды в см$$$^3$$$ в сосудах при условии, что $$$l$$$-й сосуд останется пустым.

Пример
Входные данные
4
4
1 2 3 4
5
5 3 1 5 2
6
3 4 2 6 1 5
7
1 2 1 4 2 3 5
Выходные данные
6 6 7 9 
17 16 14 14 17 
21 21 20 20 21 21 
17 17 17 17 21 21 22
Примечание

Рассмотрим первый набор входных данных.

  • Для того чтобы сосуд $$$1$$$ остался пустым, один из хороших массивов $$$w = [0, 1, 2, 3]$$$, итого $$$6$$$ см$$$^3$$$ воды.
  • Для того чтобы сосуд $$$2$$$ остался пустым, один из хороших массивов $$$w = [1, 0, 2, 3]$$$, итого $$$6$$$ см$$$^3$$$ воды.
  • Для того чтобы сосуд $$$3$$$ остался пустым, один из хороших массивов $$$w = [2, 2, 0, 3]$$$, итого $$$7$$$ см$$$^3$$$ воды.
  • Для того чтобы сосуд $$$4$$$ остался пустым, один из хороших массивов $$$w = [3, 3, 3, 0]$$$, итого $$$9$$$ см$$$^3$$$ воды.

А, например, массив $$$w = [2, 2, 0, 4]$$$ не является хорошим, так как $$$\max(w_3, w_4) \gt h_3$$$, а значит, должно выполняться $$$w_3 = w_4$$$.

Можно показать, что каждый из приведённых выше массивов имеет максимальную возможную сумму среди всех подходящих вариантов.