Collatz polinomial

Todos conhecem (ou já ouviram falar) da famosa Conjectura de Collatz: pegue um número inteiro positivo. Se ele for ı́mpar, multiplique por 3 e some 1. Se for par, divida por 2. Repita o processo até chegar em 1. Apesar de sua simplicidade, ninguém sabe provar se a sequência realmente sempre alcança 1, qualquer que seja o número inicial.

Aline, fã desse tipo de curiosidade, decidiu criar uma variação usando polinômios em vez de números. Para não complicar, ela trabalha apenas com polinômios cujos coeficientes são $0$ ou $1$, ou seja, cada potência de $x$ aparece no máximo uma vez.

A brincadeira funciona assim:

• Se o polinômio possui termo constante (um termo que não depende de $x$), Aline multiplica o polinômio por $(x + 1)$ e depois soma $1$. Caso algum coeficiente resultante seja igual a $2$, o termo correspondente é descartado (observe que coeficientes maiores que $2$ não podem surgir).
• Se o polinômio não possui termo constante, Aline divide o polinômio por $x$.

Esse processo se repete até que o polinômio se reduza a $P (x) = 1$.

Considere $P (x) = x^3 + 1$. No primeiro passo há termo constante, então calculamos: $$ (x^3 + 1) * (x + 1) + 1 = x^4 + x^3 + x + 1 + 1 $$.

Como o coeficiente do termo constante resulta em $2$, esse termo é descartado, restando: $$. x^4 + x^3 + x $$.

Em seguida, como não há termo constante, dividimos por x: $$. x3 + x2 + 1. $$.

Continuando: • Passo 3: $x^4 + x^2 + x$ • Passo 4: $x^3 + x + 1$ • Passo 5: $x^4 + x^3 + x^2$ • Passo 6: $x^3 + x^2 + x$ • Passo 7: $x^2 + x + 1$ • Passo 8: $x^3$ • Passo 9: $x^2$ • Passo 10: $x$ • Passo 11: $1$

No total, foram necessárias 11 operações para chegar ao polinômio $P (x) = 1$. Aline precisa de ajuda para estudar essa variação da Conjectura de Collatz. Como fazer essas contas manualmente é suscetı́vel a erros, escreva um programa que determine o número de operações necessárias até o polinômio se tornar $P (x) = 1$.

A primeira linha contém um inteiro $N (0 ≤ N ≤ 20)$, indicando o grau do polinômio. A segunda linha contém $N + 1$ inteiros $a^N , a^{N −1}, . . . , a_0$ (cada um igual a 0 ou 1), onde $a_i = 1$ indica que o termo $x_i$ está presente no polinômio, e $a_i = 0$ indica que não está. Note que $a_N = 1$, já que o grau do polinômio é $N$ .

Seu programa deve produzir uma única linha com o número de operações necessárias até o polinômio se tornar $P (x) = 1$. representando