Yuki är huvuddomare i International Convex Polygon Championship (ICPC). Han föreslog ett geometriproblem till tävlingen. På grund av sin bristande erfarenhet av geometri misslyckades han dock med att generera korrekta data för konvexa polygoner.
För att bevisa sin geometriska förmåga började Yuki leka med pinnar igen. Han har $n$ pinnar, där längden på den $i$-te pinnen är $a_i$. Han tänker välja minst $3$ pinnar bland dem så att dessa pinnar kan bilda en icke-degenererad konvex polygon$^*$.
Men eftersom Yuki inte kan så mycket om geometri vet han inte hur han ska välja pinnarna. Som en god vän till Yuki behöver du hjälpa honom att hitta en delmängd av pinnar sådan att:
Delmängden innehåller minst $3$ pinnar, och antalet pinnar är så stort som möjligt;
För varje delmängd av minst $3$ pinnar som väljs ur denna delmängd kan dessa pinnar bilda en icke-degenererad konvex polygon.
Eller rapportera att ingen sådan delmängd existerar.
$^*$: En icke-degenererad konvex polygon är en polygon där alla sidlängder är större än noll, inga tre hörn ligger på linje och alla innervinklar är strikt mindre än $180^\circ$.
Indata
Detta problem innehåller flera testfall.
Den första raden innehåller ett positivt heltal $t$ ($1 \le t \le 10^5$), som representerar antalet testfall.
För varje testfall:
Den första raden innehåller ett positivt heltal $n$ ($3 \le n \le 5 \cdot 10^5$).
Den andra raden innehåller $n$ positiva heltal $a_1,\ldots,a_n$ ($1 \le a_i \le 10^9$).
Det garanteras att summan av $n$ över alla testfall inte överstiger $5 \cdot 10^5$.
Utdata
För varje testfall, skriv ut en rad:
Om ingen sådan delmängd existerar, skriv ut ett enda heltal $0$.
Om en sådan delmängd existerar, skriv först ut ett heltal $k$, som representerar storleken på delmängden du hittade, följt av $k$ heltal $b_1,\ldots,b_k$, som representerar längderna på de $k$ pinnarna i din delmängd.
Exempel
Exempelindata 1
3 4 6 9 2 6 3 4 4 9 6 3 1 4 6 5 9
Exempelutdata 1
3 6 2 6 0 4 3 4 5 6
Anmärkning
För det första testfallet:
$\{6,2,6\}$ är en giltig delmängd; eftersom $2+6>6$ kan dessa $3$ pinnar bilda en icke-degenererad triangel; det är lätt att bevisa att ingen större giltig delmängd existerar.
$\{6,6,9\}$ är också en giltig delmängd.
För det andra testfallet:
- Det kan bevisas att ingen giltig delmängd existerar.
För det tredje testfallet:
$\{3,4,5,6\}$ är en giltig delmängd; i detta fall har Yuki $5$ sätt att välja pinnar: $\{3,4,5\}$, $\{3,4,6\}$, $\{3,5,6\}$, $\{4,5,6\}$, $\{3,4,5,6\}$, och varje sätt kan bilda en icke-degenererad konvex polygon; det är lätt att bevisa att ingen större giltig delmängd existerar.
$\{3,4,5,6,9\}$ är inte en giltig delmängd eftersom pinnarna med längderna $3,4,9$ inte kan bilda en icke-degenererad triangel.
$\{3,5,6\}$ är inte en giltig delmängd eftersom det finns en större giltig delmängd.