#include <bits/stdc++.h>
using namespace std;
int main(void) {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
 
    const int N = 1LL<<20,inf = 1e9;
    vector<int> a(N);
    iota(a.begin(),a.end(),0);
    a[0]=inf;
    int cnt = 0;
    const auto cmp = [&](const int &x,const int &y)->bool{
        if(x==inf||y==inf)
            cnt++;
        return x<y;
    };
    stable_sort(a.begin(),a.end(),cmp);
    cout<<"N - "<<N<<std::endl;
    cout<<"std::stable_sort worstcase - "<<cnt<<std::endl;
    return 0;
}
 

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmludCBtYWluKHZvaWQpIHsKICAgIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpO2Npbi50aWUoTlVMTCk7CgogICAgY29uc3QgaW50IE4gPSAxTEw8PDIwLGluZiA9IDFlOTsKICAgIHZlY3RvcjxpbnQ+IGEoTik7CiAgICBpb3RhKGEuYmVnaW4oKSxhLmVuZCgpLDApOwogICAgYVswXT1pbmY7CiAgICBpbnQgY250ID0gMDsKICAgIGNvbnN0IGF1dG8gY21wID0gWyZdKGNvbnN0IGludCAmeCxjb25zdCBpbnQgJnkpLT5ib29sewogICAgICAgIGlmKHg9PWluZnx8eT09aW5mKQogICAgICAgICAgICBjbnQrKzsKICAgICAgICByZXR1cm4geDx5OwogICAgfTsKICAgIHN0YWJsZV9zb3J0KGEuYmVnaW4oKSxhLmVuZCgpLGNtcCk7CiAgICBjb3V0PDwiTiAtICI8PE48PHN0ZDo6ZW5kbDsKICAgIGNvdXQ8PCJzdGQ6OnN0YWJsZV9zb3J0IHdvcnN0Y2FzZSAtICI8PGNudDw8c3RkOjplbmRsOwogICAgcmV0dXJuIDA7Cn0K