#include <assert.h>
#include <algorithm>
#include <iostream>
#include <vector>
 
using namespace std;
 
constexpr int N = 10'000'000;
 
int main() {
  std::vector<int> A(N);
  for (int l = 0, r = N, a = 2; l < r; ++a) {
    A[--r] = a;
    for (int i = 0; i < a && l < r; ++i) A[l++] = a;
  }
  auto B = A;
  cout << clock() << endl;
  sort(A.begin(), A.end());
  cout << clock() << endl;
  stable_sort(B.begin(), B.end());
  cout << clock() << endl;
  assert(A == B);
  return 0;
}
 

I2luY2x1ZGUgPGFzc2VydC5oPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDx2ZWN0b3I+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY29uc3RleHByIGludCBOID0gMTAnMDAwJzAwMDsKCmludCBtYWluKCkgewogIHN0ZDo6dmVjdG9yPGludD4gQShOKTsKICBmb3IgKGludCBsID0gMCwgciA9IE4sIGEgPSAyOyBsIDwgcjsgKythKSB7CiAgICBBWy0tcl0gPSBhOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBhICYmIGwgPCByOyArK2kpIEFbbCsrXSA9IGE7CiAgfQogIGF1dG8gQiA9IEE7CiAgY291dCA8PCBjbG9jaygpIDw8IGVuZGw7CiAgc29ydChBLmJlZ2luKCksIEEuZW5kKCkpOwogIGNvdXQgPDwgY2xvY2soKSA8PCBlbmRsOwogIHN0YWJsZV9zb3J0KEIuYmVnaW4oKSwgQi5lbmQoKSk7CiAgY291dCA8PCBjbG9jaygpIDw8IGVuZGw7CiAgYXNzZXJ0KEEgPT0gQik7CiAgcmV0dXJuIDA7Cn0K