Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии вы должны максимизировать сумму. Вы можете делать взломы только в том случае, если решили все версии этой задачи.
У вас есть массив $$$a$$$ длины $$$n$$$, состоящий из ненулевых (но, возможно, отрицательных) целых чисел. Вы выполните следующую операцию не более $$$n$$$ раз (возможно, ни разу):
Выведите корректную последовательность операций длиной не более $$$n$$$, которая $$$\color{red}{\text{максимизирует}}$$$ сумму элементов массива $$$a$$$ в конце.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — длину массива $$$a$$$.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$-10^9 \le a_i \le 10^9, a_i \ne 0$$$).
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число $$$k$$$ ($$$0 \le k \le n$$$) — количество операций, которые вы выполните.
Затем выведите $$$k$$$ целых чисел $$$b_1,\ldots,b_k$$$, где $$$b_i$$$ — индекс, на котором вы выполняете $$$i$$$-ю операцию.
После выполнения всех операций сумма элементов массива $$$a$$$ должна быть максимально возможной.
55-1 -2 -3 -5 -445 7 10 1951 -3 2 -1 10416 -13 -18 -16112 -10 -11 3 -10 15 7 18 16 17 -9
0 0 2 1 3 0 6 6 3 1 5 4 7
В первом наборе входных данных ни одной операции выполнить нельзя.
Во втором наборе входных данных сумма уже максимальна.
В третьем наборе входных данных операции выполняются следующим образом:
Сумма элементов полученного массива равна $$$11$$$. Можно доказать, что это значение является максимально возможным.
