class Solution(object):
    def lastRemaining(self, n):
        """
        :type n: int
        :rtype: int
        """

        if not n: return 0
        start, step,count=1,1,n
        end=start+(count-1)*step
        direction=1
        while count>1:
            if direction==1:
                start,step,count=start+step,step*2,count/2
                end=start+(count-1)*step
            else:
                end,step,count=end-step,step*2,count/2
                start=end-(count-1)*step
            direction*=-1
        return start