```
public int lastRemaining(int n) {
if (n == 1) return 1;
if (n < 6) return 2;
return 2 * (n / 2 + 1 - lastRemaining(n / 2));
}
```

if n is odd, the result of `[1, 2, 3, 4, 5, 6, 7, 8, 9]`

is same as `[1, 2, 3, 4, 5, 6, 7, 8]`

when n = `8`

or `9`

, the Original is :`[1, 2, 3, 4, 5, 6, 7, 8, 9]`

or `[1, 2, 3, 4, 5, 6, 7, 8]`

after step 1：the array is remain `[2, 4, 6, 8]`

, then we do from right to left, this is same like `[1, 2, 3, 4]`

, but from right to left, so the recursive solve is coding like above。