Solution
C++ []\nstatic const auto init = []{\n    cin.tie(nullptr);\n    ios::sync_with_stdio(false);\n    return false;\n}();\nint prefsum[100005];\nint psz = 0;\n\ncl
```C++ []\nstatic const auto init = []{\n    cin.tie(nullptr);\n    ios::sync_with_stdio(false);\n    return false;\n}();\nint prefsum[100005];\nint psz = 0;\n\nclass Solution {\npublic:\n    Solution(int n, vector<int>& blacklist) {\n        ::sort(begin(blacklist), end(blacklist));\n        psz = 0;\n        int pre = 0;\n        int sz = blacklist.size();\n        for (int i = 0; i < sz;) {\n            int j = i+1;\n            while (j < sz && blacklist[j] == blacklist[j-1] + 1) {++j;}\n            if (blacklist[i] != 0) {\n                intv.push_back({pre, blacklist[i]-1});\n            }\n            pre = blacklist[j-1] + 1;\n            i = j;\n        }\n        if (pre <= n-1) {\n            intv.push_back({pre, n-1});\n        }\n        total = 0;\n        for (int i = 0; i < intv.size(); ++i) {\n            int length = intv[i].second - intv[i].first + 1;\n            prefsum[psz++] = total;\n            total += length;\n        }\n    }\n    int pick() {\n        int r = rand()%total;\n        int idx = upper_bound(prefsum, prefsum+psz, r) - prefsum - 1;\n        int offset = r - prefsum[idx];\n        return intv[idx].first + offset;\n    }\n    vector<pair<int,int>> intv;\n    int total;\n};\n```\n\n```Python3 []\nimport random\n\nclass Solution:\n    def __init__(self, n, blacklist):\n        bLen = len(blacklist)\n        self.blackListMap = {}\n        blacklistSet = set(blacklist)\n\n        for b in blacklist:\n            if b >= (n-bLen):\n                continue\n            self.blackListMap[b] = None\n        \n        start = n-bLen\n        for b in self.blackListMap.keys():\n            while start < n and start in blacklistSet:\n                start += 1\n            self.blackListMap[b] = start\n            start += 1\n        self.numElements = n - bLen\n\n    def pick(self):\n        randIndex = int(random.random() * self.numElements)\n        return self.blackListMap[randIndex] if randIndex in self.blackListMap else randIndex\n```\n\n```Java []\nclass Solution {\n    Map<Integer, Integer> map;\n    Random rand = new Random();\n    int size;\n\n    public Solution(int n, int[] blacklist) {\n        map = new HashMap<>();\n        size = n - blacklist.length;\n        int last = n - 1;\n        for (int b: blacklist) {\n            map.put(b, -1);\n        }\n        for (int b: blacklist) {\n            if (b >= size) {\n                continue;\n            }\n            while (map.containsKey(last)) {\n                last--;\n            }\n            map.put(b, last);\n            last--;\n        }\n    }\n    public int pick() {\n        int idx = rand.nextInt(size);\n        if (map.containsKey(idx)) {\n            return map.get(idx);\n        }\n        return idx;\n    }\n}\n```\n
['C++', 'Java', 'Python3']