Yuki on International Convex Polygon Championship (ICPC) -kilpailun päätuomari. Hän ehdotti kilpailuun geometriatehtävää. Vähäisen geometriakokemuksensa vuoksi hän kuitenkin epäonnistui oikeanlaisen konveksien monikulmioiden testidatan luomisessa.
Todistaakseen geometriset taitonsa Yuki alkoi taas leikkiä tikuilla. Hänellä on $n$ tikkua, joista $i$:nnen tikun pituus on $a_i$. Hän aikoo valita niistä vähintään $3$ tikkua siten, että näistä tikuista voidaan muodostaa ei-degeneroitunut konveksi monikulmio$^*$.
Koska Yuki ei kuitenkaan tiedä paljoa geometriasta, hän ei osaa valita tikkuja. Yukin hyvänä ystävänä sinun tulee auttaa häntä löytämään tikkujen osajoukko siten, että:
Osajoukko sisältää vähintään $3$ tikkua, ja tikkujen lukumäärä on mahdollisimman suuri;
Mille tahansa tästä osajoukosta valitulle vähintään $3$ tikun osajoukolle pätee, että näistä tikuista voidaan muodostaa ei-degeneroitunut konveksi monikulmio.
Tai ilmoita, ettei tällaista osajoukkoa ole olemassa.
$^*$: Ei-degeneroitunut konveksi monikulmio on monikulmio, jonka kaikkien sivujen pituudet ovat suurempia kuin nolla, mitkään kolme kärkipistettä eivät ole samalla suoralla ja kaikki sisäkulmat ovat aidosti pienempiä kuin $180^\circ$.
Syöte
Tämä tehtävä sisältää useita testitapauksia.
Ensimmäinen rivi sisältää positiivisen kokonaisluvun $t$ ($1 \le t \le 10^5$), joka kuvaa testitapausten lukumäärää.
Jokaiselle testitapaukselle:
Ensimmäinen rivi sisältää positiivisen kokonaisluvun $n$ ($3 \le n \le 5 \cdot 10^5$).
Toinen rivi sisältää $n$ positiivista kokonaislukua $a_1,\ldots,a_n$ ($1 \le a_i \le 10^9$).
On taattu, että lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $5 \cdot 10^5$.
Tuloste
Tulosta jokaiselle testitapaukselle yksi rivi:
Jos tällaista osajoukkoa ei ole olemassa, tulosta yksi kokonaisluku $0$.
Jos tällainen osajoukko on olemassa, tulosta ensin kokonaisluku $k$, joka kuvaa löytämäsi osajoukon kokoa, ja sen jälkeen $k$ kokonaislukua $b_1,\ldots,b_k$, jotka kuvaavat osajoukkosi $k$ tikun pituuksia.
Esimerkki
Esimerkkisyöte 1
3 4 6 9 2 6 3 4 4 9 6 3 1 4 6 5 9
Esimerkkituloste 1
3 6 2 6 0 4 3 4 5 6
Huomautus
Ensimmäisessä testitapauksessa:
$\{6,2,6\}$ on kelvollinen osajoukko; koska $2+6>6$, näistä $3$ tikusta voidaan muodostaa ei-degeneroitunut kolmio; on helppo todistaa, ettei suurempaa kelvollista osajoukkoa ole olemassa.
$\{6,6,9\}$ on myös kelvollinen osajoukko.
Toisessa testitapauksessa:
- Voidaan todistaa, ettei kelvollista osajoukkoa ole olemassa.
Kolmannessa testitapauksessa:
$\{3,4,5,6\}$ on kelvollinen osajoukko; tässä tapauksessa Yukilla on $5$ tapaa valita tikut: $\{3,4,5\}$, $\{3,4,6\}$, $\{3,5,6\}$, $\{4,5,6\}$, $\{3,4,5,6\}$, ja jokaisella tavalla voidaan muodostaa ei-degeneroitunut konveksi monikulmio; on helppo todistaa, ettei suurempaa kelvollista osajoukkoa ole olemassa.
$\{3,4,5,6,9\}$ ei ole kelvollinen osajoukko, koska pituuksien $3,4,9$ tikuista ei voida muodostaa ei-degeneroitunutta kolmiota.
$\{3,5,6\}$ ei ole kelvollinen osajoukko, koska on olemassa suurempi kelvollinen osajoukko.