D. Максимальный многоугольник
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a$$$ длины $$$n$$$. Найдите лексикографически наибольшую$$$^{\text{∗}}$$$ подпоследовательность$$$^{\text{†}}$$$ $$$s$$$ массива $$$a$$$, такую что $$$s$$$ может быть длинами сторон многоугольника.

Напомним, что $$$s$$$ может быть длинами сторон многоугольника, если и только если $$$|s| \geq 3$$$ и

$$$$$$ 2 \cdot \max(s_1, s_2, \ldots, s_{|s|}) \lt s_1 + s_2 + \ldots + s_{|s|}. $$$$$$

Если такой подпоследовательности $$$s$$$ не существует, выведите $$$-1$$$.

$$$^{\text{∗}}$$$Последовательность $$$x$$$ лексикографически меньше последовательности $$$y$$$, если и только если выполняется одно из следующих условий:

  • $$$x$$$ является префиксом $$$y$$$, но $$$x \ne y$$$;
  • в первой позиции, где $$$x$$$ и $$$y$$$ различаются, последовательность $$$x$$$ имеет меньший элемент, чем соответствующий элемент в $$$y$$$.

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

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$) — длина массива $$$a$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — массив $$$a$$$.

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

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

Для каждого набора выведите ответ в следующем формате.

Если ответ существует, выведите следующее:

В первой строке выведите целое число $$$k$$$ ($$$1 \leq k \leq n$$$) — длину подпоследовательности $$$s$$$.

Во второй строке выведите $$$k$$$ целых чисел $$$s_1, s_2, \ldots, s_k$$$ ($$$1 \leq s_i \leq 10^9$$$, $$$s$$$ является подпоследовательностью $$$a$$$) — подпоследовательность $$$s$$$. Обратите внимание, что необходимо выводить значения, а не индексы.

В противном случае выведите одну строку с целым числом $$$-1$$$.

Пример
Входные данные
5
3
3 1 2
4
1 4 2 3
6
1 6 4 5 3 2
6
43 12 99 53 22 4
7
9 764 54 73 22 23 1
Выходные данные
-1
3
4 2 3 
4
6 5 3 2 
5
43 99 53 22 4 
4
54 73 23 1
Примечание

В первом наборе нет подпоследовательностей, которые могут быть длинами сторон многоугольника.

Во втором наборе есть $$$2$$$ подпоследовательности, которые могут быть длинами сторон многоугольника: $$$1, 4, 2, 3$$$ и $$$4, 2, 3$$$. Вторая является лексикографически большей подпоследовательностью.