typedef pair <int, int> pii;

const int N = (int)1.1e6

int n;
pii t[2 * N];

int zero()
{
  return (int)2e9;
}

pii f( pii a, pii b )
{
  return min(a, b);
}

// O(logn)
void change( int i, int x )
{
  t[i += n] = pii(x, i);
  for (i /= 2; i >= 1; i /= 2)
    t[i] = f(t[2 * i], t[2 * i + 1]);  
}

// O(log|r-l|)   l=r => O(1)
// O(logn)
int get( int l, int r )
{
  int minimum = zero();
  for (l += n, r += n; l <= r; l /= 2, r /= 2)
  {
    if (l % 2 == 1) minimum = f(minimum, t[l++]);
    if (r % 2 == 0) minimum = f(minimum, t[r--]);
  }
  return minimum; 
}

void build( int k, int *a )
{
  n = k;
  forn(i, k)
    t[i + n] = pii(a[i], i); // n - k
  for (int i = n - 1; i >= 1; i--)
    t[i] = f(t[2 * i],t[2 * i + 1]);  
}

void sort( int k, int *a )
{
  build(k, a);
  forn(i, k)
  {
    pii p = get(0, k - 1);
    a[i] = p.first;
    change(p.second, zero());
  }
}