c++ solution, O(1) extra space, O(log(blacklist.size)) pick time
```\nclass Solution \n{\n    vector bl;\n    std::default_random_engine generator;\n    std::uniform_int_distribution distribution;\npublic:\n    Solution(int N
```\nclass Solution \n{\n    vector<int> bl;\n    std::default_random_engine generator;\n    std::uniform_int_distribution<int> distribution;\npublic:\n    Solution(int N, vector<int> blacklist)\n    {\n        swap(bl, blacklist);\n        sort(bl.begin(), bl.end());\n        for (int i = 0, e = bl.size(); i < e; ++i)\n            bl[i] -= i;\n        \n        distribution = std::uniform_int_distribution<int>(0, N - 1 - bl.size());\n    }\n    \n    int pick() {\n        auto r = distribution(generator);\n        return r + (upper_bound(bl.begin(), bl.end(), r) - bl.begin());\n    }\n};\n
[]