Fent els nombres iguals P54072

Tenim una col·lecció d’$n$ nombres naturals. Repetidament, podem escollir dos nombres $x$ i $y$, amb $x < y$, esborrar $y$ de la col·lecció, i afegir-hi $x$ i $y - x$. L’objectiu és aconseguir que tots els nombres siguin iguals.

Per exemple, si tenim $\{2, 4, 6\}$, podem escollir $x = 4$ i $y = 6$, passant a $\{2, 2, 4, 4\}$, escollir $x = 2$ i $y = 4$, passant a $\{2, 2, 2, 2, 4\}$, i tornar a escollir $x = 2$ i $y = 4$, passant a $\{2, 2, 2, 2, 2, 2\}$. Es pot comprovar que no és possible fer que tots els nombres siguin iguals amb menys de tres passos.

En general, quin és el mínim nombre de passos necessari?

Entrada

L’entrada conté diversos casos. Cada cas comença amb una $n$ entre 1 i $10^5$, seguida dels $n$ nombres, tots entre 1 i $10^9$.

Sortida

Per a cada cas, escriviu quants passos calen per fer tots els nombres iguals.