class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int> res;
        res.push_back(1);

        for(int i = 2 ; i <= N ; i++)
        {
            int l = 0 , r = res.size() - 1;
            while(l < r)//二分找出小于i的最大值的位置
            {
                int mid = l + r + 1 >> 1;
                if(compare(res[mid] , i)) l = mid;//询问i与res[mid]的关系
                else r = mid - 1;
            }

            res.push_back(i);//将i插入最后
            for(int j = res.size() - 2 ; j > r ; j--) swap(res[j] , res[j + 1]);//通过一直swap将i交换至res[r+1]
            if(!compare(res[r] , i))  swap(res[r] , res[r + 1]);//如果i小于所有原数列的数，要再跟第一个数交换一下
        }                                                    
/*
一、if里的r不能用0替换，因为这里的数不具有传递性，所以如果i已经放好位置，但是i仍可能比res[0]小，但是此时是不用交换的，
而且此时不知道i的位置，所以就算要交换也不知道位置，所以if里的l不能用0替换;
二、swap中的r可用0替换，因为如果满足了if的判断条件，说明i的确比所有的数小，此时l就是0。
就相当于，要进自己的房间，给房间上了锁(条件严格，如果有钥匙(满足条件)，进了房间可以随便折腾，因为你是主人(填r也好，填0也好)
但是不能把房门打开(降低标准)，因为进来的就可能不是主人。
*/        
        return res;
    }
};