假设当前已经排好了 $1,2,…,k$ 的顺序，考虑当前第 $k+1$ 个元素应该插入的位置。

我们可以二分插入位置 $mid$，如果 $mid$ 比 $i$ 小，那么 $l = mid$, 否则 $r = mid - 1$。

可以证明如此二分一定能成功插入，证明如下：

如果第 $k$ 个元素比第 $mid$ 个元素小，那么我们可以寻找第 $mid - 1$ 个元素。如果第 $k$ 个元素比第 $mid-1$ 个元素大，那么第 $k$ 个元素就插入到 $mid - 1$ 和 $mid - 2$ 之间；否则我们就继续往前找，直到第 $1$ 个元素，如果比第 $1$ 个元素小，那我们就插在第 $1$ 个元素前面。

反之，若第 $k$ 个元素大于第 $mid$ 个元素，同上亦可证明。

虽然我们二分时不会像上方一个一个枚举，但也足够证明二分的正确性。

// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.

class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int> res(1, 1);
        for (int i = 2; i <= N; i ++) {
            int l = 0, r = res.size() - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (compare(res[mid], i)) l = mid;
                else r = mid - 1;
            }
            res.push_back(i);
            for (int j = res.size() - 2; j > r; j --) swap(res[j], res[j + 1]);
            if (compare(i, res[r])) swap(res[r], res[r + 1]);
        }
        return res;
    }
};