# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# The Mughal Emperor

By Amateur · Limits 1s, 512 MB

You all must’ve heard the name of the emperor Humayun Mirza. He was a very kind human being. But this kindness turned out to be his biggest weak point. Once, he was defeated and captured by the clever Sher Kha. The emperor was kept in a cave with some of his soldiers. Humayun came up with a plan to retain their honor. He and his soldiers stood in a circle that is the 1st person is neighbor of 2nd and the nth. Now, the 1st person killed his neighbor ( 2nd ).Then the 3rd killed the 4th and so on until there is only one person alive. As Humayun not being good in math he asked for your help. Given the number of his soldiers you must tell him which position he should stand to stay alive. The number of soldiers will be (N) 0<=N<1000000000.

## Sample

InputOutput
```1
2
3
```
```1
3
1
```

### Statistics

56% Solution Ratio

exitkhanEarliest, 3w ago

exitkhanFastest, 0.0s

exitkhanLightest, 0 B

mdvirusShortest, 87B