932

class Solution {
public:
    unordered_map<int, vector<int>> memo;
    vector<int> beautifulArray(int n) {
        return solve(n);
    }

    vector<int> solve(int n){
        if(memo.count(n))
            return memo[n];

        vector<int> ans;
        if(n == 1){
            ans.push_back(1);
        }
        else{
            // Have all odd integers on left.
            for(int num: solve((n+1)/2))
                ans.push_back(2*num-1);

            // Have all even integers on right.
            for(int num: solve(n/2))
                ans.push_back(2*num);
        }
        memo[n] = ans;
        return ans;
    }
};