Negociação Poliedral

Mario e Wario se encontraram de surpresa na torre principal do castelo do mundo 8, depois de derrotarem o malvado Bowser. Dentro de um de seus baús secretos havia uma grande surpresa: $n$ poliedros com valores capazes de tornar milionário qualquer habitante do Reino dos Cogumelos!

A magia desses poliedros estava em permitir que seu portador adquirisse qualquer poder: o da flor de fogo, transformar-se em tanuki, estrela, entre muitos outros, e por isso eram objetos muito procurados pelos aventureiros do reino.

No fim das contas, a razão pela qual os poliedros eram tão valiosos, além de seus poderes, era que cada um deles era vendido por uma quantidade enorme de moedas. Os poliedros do baú são numerados de $0$ a $n-1$, e o $i$-ésimo deles vale $2^i$ moedas.

Como Mario e Wario chegaram ao mesmo tempo à sala do baú, o primeiro instinto dos dois foi duelar para decidir quem ficaria com o tesouro. No entanto, ambos estavam cansados demais da longa aventura, então se sentaram para fazer uma chuva de ideias.

Uma das ideias vencedoras foi dividir os poliedros da forma mais justa possível; isto é, de modo que a diferença absoluta entre o que cada um ganharia vendendo todos os seus poliedros fosse a mínima possível.

Se Mario e Wario tivessem energia suficiente para encontrar essa divisão justa, eles a teriam gastado se enfrentando em um mano a mano em vez de negociar. Isso significa que será seu trabalho determinar qual é a mínima diferença absoluta que eles podem alcançar.

Entrada

A primeira linha contém um inteiro $n$ ($1 \leq n \leq 10^6$), o número de poliedros no baú.

Saída

Imprima um único inteiro: a mínima diferença absoluta que Mario e Wario podem alcançar ao dividir os poliedros em dois grupos.

Notas

No exemplo, os poliedros valem $1$, $2$ e $4$ moedas. Se um deles ficar com o de $4$ e o outro com os de $1$ e $2$, a diferença é $4 - 3 = 1$, e não é possível obter uma diferença menor.

3

1