На крајот на долгиот работен ден на фабричката лента се останати N роботчиња (на позиции од 1 до N) кои Миле и Емил треба да ги спакуваат.

Миле се наоѓа на почеток на лентата (кај позиција 1), а Емил на крај на лентата (кај позиција N). За да им биде поинтересно, одлучиле да ги пакуваат роботчињата според следниот алгоритам:

Прво Миле ќе тргне од неговата страна (од почеток) и ќе го спакува секое второ роботче.

Потоа, Емил ќе тргне од неговата страна (од крај) и ќе го спакува секое второ роботче од преостанатите роботчиња.

Потоа пак Миле почнува од почеток… па Емил, и се така дури не се спакува последното роботче.

Ваша задача е да ја утврдите позицијата на последното спакувано роботче.

Влез

Во еден и единствен ред е даден бројот на роботчиња N (1 ≤ N ≤ 10¹⁶).

Забелешка.
За 50% од поените важи: 1 ≤ N ≤ 10 000

Излез

Во еден и единствен ред отпечатете ја бараната позиција.

Ограничувања

Временско ограничување: 100 milliseconds
Мемориско ограничување: 64 megabytes

Примери

влез
10

излез
9

Објаснување за првиот пример.
На почеток лентата изгледа вака:

После првото пакување на Миле (откако Миле ќе помине од лево кон десно):

После првото пакување на Емил (откако Емил ќе помине од десно кон лево):

После второто пакување на Миле (откако Миле ќе помине од лево кон десно):

После второто пакување на Емил (откако Емил ќе помине од десно кон лево):

На крај е останато роботчето на позиција 9.