#include "/home/judge/data/1948/grader.cpp"
vector<int> Solution::specialSort(int N) {
    vector<int> a;//a来装答案
    //...你的代码 
    a.push_back(1);
    for(int i=2;i<=N;i++)
    {
        int l=0, r=a.size()-1, p=-1;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(compare(a[mid],i)) {
                l=mid+1;
                p=mid;
            } else {
                r=mid-1;
            }
        }
        a.push_back(i);
        for(int j=a.size()-2;j>p;j--) {
            swap(a[j],a[j+1]);
        }
    }
    return a;
}

#include "/home/judge/data/1948/grader.cpp"
vector<int> Solution::specialSort(int N) {
    vector<int> a;//a来装答案
    //...你的代码 
    a.push_back(1);
    for(int i=2;i<=N;i++)
    {
        int l=0,r=a.size()-1,p=-1;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(compare(a[mid],i))l=mid+1,p=mid;
            else r=mid-1;
        }
        a.push_back(i);
        for(int j=a.size()-2;j>p;j--)swap(a[j],a[j+1]);
    }
    return a;
}