class Solution {
public:
    int lastRemaining(int n) {
        if (n==0)
            return 0;
        std::vector<int> cnt(n);
        std::iota(cnt.begin(), cnt.end(), 1);
        std::list<int> stk (cnt.begin(),cnt.end());

        bool front=true;
        while(stk.size()>1) {
            if (front) {
                front=false;
                int numElems = stk.size();
                while(numElems-- > 0) {
                    stk.pop_front();
                    if (--numElems >= 0)
                        stk.splice(stk.end(), stk, stk.begin());
                }
            }
            else {
                front=true;
                int numElems = stk.size();
                while(numElems-- > 0) {
                    stk.pop_back();
                    if (--numElems >= 0)
                        stk.splice(stk.begin(), stk, --stk.end());
                }
            }
        }
        return stk.front();
    }
};