Globglogabgalab P48500

0.72 Una biblioteca té $n$ passadissos, numerats en ordre de l’1 a l’$n$. A un dels passadissos s’amaga en Globglogabgalab (Glob, per abreujar). Sense mirar, des de fora de la biblioteca, i repetidament, podeu triar un número de passadís i preguntar a crits al Glob si es troba allà. Si encerteu, ja heu acabat. Altrament, en Glob es mourà a un dels (com a molt) dos passadissos adjacents al que es troba actualment. El vostre objectiu és triar una seqüència de números de la mínima longitud $\ell(n)$ que us garanteixi que encertareu en algun moment on està en Glob.

0.28

Per exemple, tenim $\ell(3) = 2$, perquè per a $n = 3$ la seqüència 2 2 és òptima: Si en Glob estava inicialment al passadís 2, a la primera ja estem. Altrament, al principi en Glob estava al passadís 1 o 3, per la qual cosa en el segon moment estarà segur en el 2. I és trivial veure que no es pot aconseguir trobar amb seguretat en Glob amb un sol intent.

Per a cada $n$ donada, quant val $\ell(n)$?

Entrada

L’entrada consisteix en una línia amb un natural $m$ entre 0 i $10^4$, seguit d’$m$ línies, cadascuna amb una $n$ entre 1 i $10^6$.

Sortida

Per a cada $n$, cal escriure una línia amb $\ell(n)$.