Màxim nombre en base tres P51176

Considereu la representació en base tres dels nombres naturals. Per exemple, 59 es representa com 2012, perquè 2 · 3³ + 0 · 3² + 1 · 3¹ + 2 · 3⁰ = 59. Fixeu-vos que tots els dígits estan entre 0 i 2, i que no tenim zeros a l’esquerra.

Feu un programa que escrigui el resultat de reordenar els dígits en base tres de cada nombre donat, de manera que el resultat sigui el màxim possible, amb una condició addicional: no podem tenir dos dígits consecutius iguals.

Entrada

L’entrada consisteix en diverses n, totes entre 1 i 10¹⁸.

Sortida

Per a cada n donada, escriviu-ne la reordenació dels dígits en base tres que produeixi el màxim resultat possible, i que no tingui dígits adjacents iguals. Si no hi ha cap reordenació possible, cal indicar-ho.