G2. Загадай желание при виде спутника (сложная версия)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии $$$t \le 10^4$$$, $$$n \le 5 \cdot 10^5$$$ и сумма $$$n$$$ не превосходит $$$5 \cdot 10^5$$$. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Для непустой последовательности $$$c$$$ длины $$$k$$$ определим $$$f(c)$$$ следующим образом:

  • Черепаха и Хрюшка играют в игру на последовательности. Им дана последовательность $$$c_1, c_2, \ldots, c_k$$$, и первой ходит Черепаха. Черепаха и Хрюшка поочередно делают ходы (то есть, Черепаха делает первый ход, Хрюшка делает второй, Черепаха делает третий и так далее).
  • Игра проходит следующим образом:
    • Пусть текущая длина последовательности равна $$$m$$$. Если $$$m = 1$$$, игра заканчивается.
    • Если игра не закончилась и ходит Черепаха, то Черепаха должна выбрать целое число $$$i$$$ такое, что $$$1 \le i \le m - 1$$$, сделать $$$c_i$$$ равным $$$\min(c_i, c_{i + 1})$$$ и удалить $$$c_{i + 1}$$$.
    • Если игра не закончилась и ходит Хрюшка, то Хрюшка должна выбрать целое число $$$i$$$ такое, что $$$1 \le i \le m - 1$$$, сделать $$$c_i$$$ равным $$$\max(c_i, c_{i + 1})$$$ и удалить $$$c_{i + 1}$$$.
  • Черепаха хочет максимизировать значение $$$c_1$$$ в конце, в то время как Хрюшка хочет минимизировать значение $$$c_1$$$ в конце.
  • $$$f(c)$$$ — это значение $$$c_1$$$ в конце, если оба игрока играют оптимально.

Для перестановки $$$p$$$ длины $$$n$$$$$$^{\text{∗}}$$$ Черепаха определяет красоту перестановки как $$$\sum\limits_{i = 1}^n \sum\limits_{j = i}^n f([p_i, p_{i + 1}, \ldots, p_j])$$$ (то есть, сумма $$$f(c)$$$, где $$$c$$$ — это непустой подотрезок$$$^{\text{†}}$$$ $$$p$$$).

Хрюшка дает Черепахе перестановку $$$a$$$ длины $$$n$$$, в которой некоторые элементы отсутствуют и представлены как $$$0$$$.

Черепаха просит вас определить перестановку $$$b$$$ длины $$$n$$$ такую, что:

  • $$$b$$$ может быть сформирована путем заполнения отсутствующих элементов $$$a$$$ (то есть, для всех $$$1 \le i \le n$$$, если $$$a_i \ne 0$$$, то $$$b_i = a_i$$$).
  • Красота перестановки $$$b$$$ максимальна.

Для удобства вам нужно только найти максимальную красоту такой перестановки $$$b$$$.

$$$^{\text{∗}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

$$$^{\text{†}}$$$Последовательность $$$a$$$ является подотрезком последовательности $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) элементов с начала и нескольких (возможно, ни одного или всех) элементов с конца.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n$$$). Гарантируется, что элементы $$$a$$$, которые не равны $$$0$$$, различны.

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

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

Для каждого набора входных данных выведите одно целое число — максимальную красоту перестановки $$$b$$$.

Пример
Входные данные
8
2
1 0
3
0 0 0
3
0 1 0
5
3 2 4 5 1
7
0 3 2 5 0 0 0
10
1 2 6 5 8 9 0 0 0 0
5
0 4 1 0 0
5
0 1 5 2 3
Выходные данные
4
12
11
44
110
300
45
40
Примечание

В первом наборе перестановка $$$b$$$ с максимальной красотой — это $$$[1, 2]$$$. Красота $$$[1, 2]$$$ равна $$$4$$$, так как $$$f([1]) + f([2]) + f([1, 2]) = 1 + 2 + 1 = 4$$$. Если $$$c = [1, 2]$$$, то $$$f(c) = 1$$$, так как Черепаха может выбрать только $$$i = 1$$$, и она установит $$$c_1$$$ в $$$\min(c_1, c_2) = 1$$$.

Во втором наборе одна из перестановок $$$b$$$ с максимальной красотой — это $$$[3, 2, 1]$$$. Красота $$$[3, 2, 1]$$$ равна $$$12$$$, так как $$$f([3]) + f([2]) + f([1]) + f([3, 2]) + f([2, 1]) + f([3, 2, 1]) = 3 + 2 + 1 + 2 + 1 + 3 = 12$$$.

В третьем наборе одна из перестановок $$$b$$$ с максимальной красотой — это $$$[2, 1, 3]$$$.

В четвертом тесте, если $$$c = [3, 2, 4, 5, 1]$$$, то $$$f(c) = 3$$$. Один из возможных процессов игры выглядит следующим образом:

  • Черепаха может выбрать $$$i = 3$$$. Тогда она установит $$$c_3$$$ в $$$\min(c_3, c_4) = 4$$$ и удалит $$$c_4$$$. Последовательность $$$c$$$ станет $$$[3, 2, 4, 1]$$$.
  • Хрюшка может выбрать $$$i = 1$$$. Тогда она установит $$$c_1$$$ в $$$\max(c_1, c_2) = 3$$$ и удалит $$$c_2$$$. Последовательность $$$c$$$ станет $$$[3, 4, 1]$$$.
  • Черепаха может выбрать $$$i = 2$$$. Тогда она установит $$$c_2$$$ в $$$\min(c_2, c_3) = 1$$$ и удалит $$$c_3$$$. Последовательность $$$c$$$ станет $$$[3, 1]$$$.
  • Хрюшка может выбрать $$$i = 1$$$. Тогда она установит $$$c_1$$$ в $$$\max(c_1, c_2) = 3$$$ и удалит $$$c_2$$$. Последовательность $$$c$$$ станет $$$[3]$$$.
  • Длина последовательности становится $$$1$$$, так что игра заканчивается. Значение $$$c_1$$$ в конце будет $$$3$$$.

В пятом наборе одна из перестановок $$$b$$$ с максимальной красотой — это $$$[1, 3, 2, 5, 6, 4, 7]$$$.