Yuki jest sędzią głównym Międzynarodowych Mistrzostw Wielokątów Wypukłych (ICPC). Zaproponował na zawody zadanie geometryczne. Jednak z powodu braku doświadczenia w geometrii nie udało mu się wygenerować poprawnych danych wielokątów wypukłych.
Aby dowieść swoich umiejętności geometrycznych, Yuki znów zaczął bawić się patykami. Ma $n$ patyków, a długość $i$-tego wynosi $a_i$. Zamierza wybrać co najmniej $3$ z nich tak, aby można było z nich utworzyć niezdegenerowany wielokąt wypukły$^*$.
Ponieważ jednak Yuki nie zna dobrze geometrii, nie wie, jak wybrać patyki. Jako jego dobry przyjaciel musisz pomóc mu znaleźć podzbiór patyków taki, że:
Podzbiór zawiera co najmniej $3$ patyki, a liczba patyków jest jak największa;
Z dowolnego podzbioru co najmniej $3$ patyków wybranych z tego podzbioru można utworzyć niezdegenerowany wielokąt wypukły.
Lub zgłoś, że taki podzbiór nie istnieje.
$^*$: Niezdegenerowany wielokąt wypukły to wielokąt, w którym wszystkie boki mają dodatnią długość, żadne trzy wierzchołki nie są współliniowe, a wszystkie kąty wewnętrzne są ściśle mniejsze niż $180^\circ$.
Wejście
Zadanie zawiera wiele przypadków testowych.
Pierwszy wiersz zawiera dodatnią liczbę całkowitą $t$ ($1 \le t \le 10^5$), oznaczającą liczbę przypadków testowych.
Dla każdego przypadku testowego:
Pierwszy wiersz zawiera dodatnią liczbę całkowitą $n$ ($3 \le n \le 5 \cdot 10^5$).
Drugi wiersz zawiera $n$ dodatnich liczb całkowitych $a_1,\ldots,a_n$ ($1 \le a_i \le 10^9$).
Zagwarantowano, że suma $n$ po wszystkich przypadkach testowych nie przekracza $5 \cdot 10^5$.
Wyjście
Dla każdego przypadku testowego wypisz jeden wiersz:
Jeśli taki podzbiór nie istnieje, wypisz jedną liczbę całkowitą $0$.
Jeśli taki podzbiór istnieje, najpierw wypisz liczbę całkowitą $k$, oznaczającą rozmiar znalezionego podzbioru, a następnie $k$ liczb całkowitych $b_1,\ldots,b_k$, oznaczających długości $k$ patyków w tym podzbiorze.
Przykład
Wejście 1
3 4 6 9 2 6 3 4 4 9 6 3 1 4 6 5 9
Wyjście 1
3 6 2 6 0 4 3 4 5 6
Uwagi
Dla pierwszego przypadku testowego:
$\{6,2,6\}$ jest poprawnym podzbiorem; ponieważ $2+6>6$, te $3$ patyki mogą utworzyć niezdegenerowany trójkąt; łatwo udowodnić, że większy poprawny podzbiór nie istnieje.
$\{6,6,9\}$ również jest poprawnym podzbiorem.
Dla drugiego przypadku testowego:
- Można udowodnić, że nie istnieje poprawny podzbiór.
Dla trzeciego przypadku testowego:
$\{3,4,5,6\}$ jest poprawnym podzbiorem; w tym przypadku Yuki ma $5$ sposobów wyboru patyków: $\{3,4,5\}$, $\{3,4,6\}$, $\{3,5,6\}$, $\{4,5,6\}$, $\{3,4,5,6\}$, a każdy z nich pozwala utworzyć niezdegenerowany wielokąt wypukły; łatwo udowodnić, że większy poprawny podzbiór nie istnieje.
$\{3,4,5,6,9\}$ nie jest poprawnym podzbiorem, ponieważ patyki o długościach $3,4,9$ nie mogą utworzyć niezdegenerowanego trójkąta.
$\{3,5,6\}$ nie jest poprawnym podzbiorem, ponieważ istnieje większy poprawny podzbiór.