Yuki est le juge en chef du Championnat international des polygones convexes (ICPC). Il a proposé un problème de géométrie pour la compétition. Cependant, faute d'expérience en géométrie, il n'a pas réussi à générer des données correctes de polygones convexes.
Pour prouver ses capacités en géométrie, Yuki s'est remis à jouer avec des bâtons. Il possède $n$ bâtons, dont le $i$-ème a une longueur $a_i$. Il compte en choisir au moins $3$ de façon qu'ils puissent former un polygone convexe non dégénéré$^*$.
Cependant, comme Yuki ne connaît pas bien la géométrie, il ne sait pas comment choisir les bâtons. En tant que bon ami de Yuki, vous devez l'aider à trouver un sous-ensemble de bâtons tel que :
Le sous-ensemble contienne au moins $3$ bâtons et que le nombre de bâtons soit aussi grand que possible ;
Pour tout sous-ensemble d'au moins $3$ bâtons choisi dans ce sous-ensemble, ces bâtons puissent former un polygone convexe non dégénéré.
Ou indiquez qu'un tel sous-ensemble n'existe pas.
$^*$ : Un polygone convexe non dégénéré est un polygone dont toutes les longueurs des côtés sont strictement positives, dont aucun groupe de trois sommets n'est aligné et dont tous les angles intérieurs sont strictement inférieurs à $180^\circ$.
Entrée
Ce problème contient plusieurs cas de test.
La première ligne contient un entier positif $t$ ($1 \le t \le 10^5$), le nombre de cas de test.
Pour chaque cas de test :
La première ligne contient un entier positif $n$ ($3 \le n \le 5 \cdot 10^5$).
La deuxième ligne contient $n$ entiers positifs $a_1,\ldots,a_n$ ($1 \le a_i \le 10^9$).
Il est garanti que la somme des $n$ sur tous les cas de test ne dépasse pas $5 \cdot 10^5$.
Sortie
Pour chaque cas de test, affichez une ligne :
Si un tel sous-ensemble n'existe pas, affichez un unique entier $0$.
S'il existe, affichez d'abord un entier $k$, la taille du sous-ensemble trouvé, suivi de $k$ entiers $b_1,\ldots,b_k$, les longueurs des $k$ bâtons de votre sous-ensemble.
Exemples
Entrée 1
3 4 6 9 2 6 3 4 4 9 6 3 1 4 6 5 9
Sortie 1
3 6 2 6 0 4 3 4 5 6
Remarque
Pour le premier cas de test :
$\{6,2,6\}$ est un sous-ensemble valide ; puisque $2+6>6$, ces $3$ bâtons peuvent former un triangle non dégénéré ; il est facile de prouver qu'aucun sous-ensemble valide plus grand n'existe.
$\{6,6,9\}$ est également un sous-ensemble valide.
Pour le deuxième cas de test :
- On peut démontrer qu'aucun sous-ensemble valide n'existe.
Pour le troisième cas de test :
$\{3,4,5,6\}$ est un sous-ensemble valide ; dans ce cas, Yuki a $5$ façons de choisir des bâtons : $\{3,4,5\}$, $\{3,4,6\}$, $\{3,5,6\}$, $\{4,5,6\}$, $\{3,4,5,6\}$, et chacune permet de former un polygone convexe non dégénéré ; il est facile de prouver qu'aucun sous-ensemble valide plus grand n'existe.
$\{3,4,5,6,9\}$ n'est pas un sous-ensemble valide, car les bâtons de longueurs $3,4,9$ ne peuvent pas former un triangle non dégénéré.
$\{3,5,6\}$ n'est pas un sous-ensemble valide, car il existe un sous-ensemble valide plus grand.