[Question]
  [
## Introduction
Some of you may have heard of [Hilbert's Grand Hotel](https://en.wikipedia.org/wiki/Hilbert's_paradox_of_the_Grand_Hotel). The manager there has lost his list of where the guests are staying but he still has the order in which they checked in. Each guest can not stay in a room with a room number less than their value and if a guest is added to a lower room, all guests in higher rooms with no empty space between them and the new guest are shifted up one room. Can you help him find where each of the guests are staying?
## Requirements
Write a program which receives an ordered list of natural numbers as input and places them at their index. If there is already a value in that index, it is shifted up to the next entry in the list. This process repeats until the first empty (0 or undefined) space is found. Any undefined spaces between the current highest index and any new input will be filled by adding 0s. As this is Hilbert's Grand Hotel, rooms higher than the current highest occupied index do not exist.
## Input and Output
Input will be an ordered list of natural numbers (allowed to be read through any accepted form of input)  
Each number in the input is considered one guest arriving at the hotel and is in order of arrival 
Output will be the final arrangement of guests (numbers) 
## Examples
> 
> **Input:** 1 3 1  
> 
> **Output:** 1 1 3  
> 
> **Step by step:**  
> 
>  1  
> 
>  Create room at index 1 and place 1 in it  
> 
>  1 0 3  
> 
>  Create rooms up to index 3 and place 3 in room 3  
> 
>  1 1 3  
> 
>  Shift the contents of room 1 up one room and place 1 in room 1 
> 
> 
> **Input:** 1 4 3 1 2 1  
> 
> **Output**: 1 1 2 1 3 4  
> 
> **Step by step:**  
> 
>  1  
> 
>  Create room at index 1 and place 1 in it  
> 
>  1 0 0 4  
> 
>  Create rooms up to index 4 and place 4 in room 4  
> 
>  1 0 3 4  
> 
>  Place 3 in room 3  
> 
>  1 1 3 4  
> 
>  Shift contents of room 1 up one room and place 1 in room 1  
> 
>  1 2 1 3 4  
> 
>  Shift contents of rooms 2 to 4 up one room and place 2 in room 2  
> 
>  1 1 2 1 3 4  
> 
>  Shift contents of rooms 1 to 5 up one room and place 1 in room 1 
> 
> 
> **Input:** 10  
> 
> **Output:** 0 0 0 0 0 0 0 0 0 0 10  
> 
> **Step by step:**  
> 
>  0 0 0 0 0 0 0 0 0 10  
> 
>  Create rooms up to room 10 and place 10 in room 10
> 
> 
> Notes:  
> 
>  Working with 0 indexed is fine and you may insert a 0 at the front of the output in that case
> 
> 
> 
[Standard loopholes](https://codegolf.meta.stackexchange.com/questions/1061/loopholes-that-are-forbidden-by-default) are forbidden, shortest code in bytes wins
  
[Answer]
# PHP 93 bytes
```
for(;$r=$g?$r+1:$g=$argv[++$i];[$g,$h[$r]]=[$h[$r],$g])$h=array_pad($h?:[],$g,0);print_r($h);
```
0 indexed. Uses a 2 in 1 loop that looks up the next guest after it gets a 0 (or a null form going beyond the current final room). Use like:
```
php -r "for(;$r=$g?$r+1:$g=$argv[++$i];[$g,$h[$r]]=[$h[$r],$g])$h=array_pad($h?:[],$g,0);print_r($h);" 1 4 3 1 2 1
```
Ungolfed:
```
for( $hotel = []; $room = $guest = $argv[ ++$i ]; )
{
    for( $hotel = array_pad( $hotel, $guest, 0 ); $guest; $room++ )
    {
        $last = $hotel[ $room ];
        $hotel[ $room ] = $guest;
        $guest = $last;
    }
}
print_r( $hotel );
```
[Answer]
# [Haskell](https://www.haskell.org/), 107 bytes
```
h=foldl(\h n->let{(b,a)=splitAt n h;(c,d)=span(>0)a;e=0:e;f=take n$b++e;g(0:m)=m;g m=m}in f++[n]++c++g d)[]
```
[Try it online!](https://tio.run/nexus/haskell#FcixDsIgEADQX7mhA@TOhKpTyTXxOyoDbWkhwtkom/HbMb7xtcjbM69Z3SPIacyhftRMXvP7yKneKghEqxZa/@NFjUZ7G9gMwW5c/SOAdDNisLsyQ9Fc7A6FyzcJbIiTOMQFcYdVT64Vn4SPV5LaxamnK12opzP1rv0A "Haskell – TIO Nexus")
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), ~~24~~ 22 bytes
```
aŻƤSƇḢßoɓ@ooƑ?
Ṭ×)ç@ƒ0
```
[Try it online!](https://tio.run/##y0rNyan8/z/x6O5jS4KPtT/csejw/PyTkx3y849NtOd6uHPN4emah5c7HJtk8P9wu7dm5P//0YY6xjqGsTpA2gTE0jGC8AxiAQ "Jelly – Try It Online")
I still have the strangest feeling that something closer to Dennis's answer should beat this, but I haven't had any luck with that so far. I have twisted the first line into something that sounds like some kind of exploding can (from [my original recursive solution](https://tio.run/##y0rNyan8/z//8PzEo7uPLQk@1v5wx6JT3SenO@TnH5toz/Vw55rD0zUPLz82yeD/4XZvzcj//6MNdYx1DGN1gLQJiKVjBOEZxAIA); I thought it saved a byte but I didn't look at the output too carefully so it actually ties but it does look funnier).
```
aŻƤSƇḢßoɓ@ooƑ?    Helper link: add a pre-positioned guest to the hotel
        ɓ         With reversed arguments (hotel left, guest right):
           oƑ?    Unless both arrays have a nonzero at the same location,
          o       return with the guest placed in its empty room;
        ɓ         if they do:
         @        (guest left, hotel right)
a                 Overlay the guest's zeroes on the hotel.
 ŻƤ               Prepend another zero to each prefix,
   SƇḢ            and take the first with a nonzero sum.
      ß           Call this link again with that as the new guest
       o          and with the hotel having the previous guest replace the new one.
Ṭ×)ç@ƒ0    Main link
  )        For each guest value,
Ṭ          obtain a list of all zeroes then a one at that index,
 ×         and multiply that by the same guest value.
     ƒ0    Starting with 0, reduce that by
   ç@      the helper with reversed arguments.
```
Essentially just boots occupants out of their rooms in sequence until there's no collision, considering a new guest as equivalent to someone evicted from the last room they can't start in.
Dennis's answer with some simple golfs for fair comparison, and an explanation for those still wondering:
# [Jelly](https://github.com/DennisMitchell/jelly), 26 bytes
```
’⁹ḣ;⁸;ṫ@œṡ0Fɗð0ẋ;@
ç@ƒ0œr0
```
[Try it online!](https://tio.run/##y0rNyan8//9Rw8xHjTsf7lhs/ahxh/XDnasdjk5@uHOhgdvJ6Yc3GDzc1W3twHV4ucOxSQZHJxcZ/D/c7q0Z@f9/tKGOgrGOgmGsjgKIaQLh6SgYwcQMYgE "Jelly – Try It Online")
```
’⁹ḣ;⁸;ṫ@œṡ0Fɗð0ẋ;@    Helper link: add a guest on the left to the hotel on the right
             ð        Let the right argument to the rest of the link be
              0ẋ      zero repeated by the value of the guest
                ;@    concatenated to the end of the hotel.
 ⁹ḣ                   Take elements from that right argument numbering
’                     one less than the guest,
   ;⁸                 concatenate the guest,
     ;      ɗ         and concatenate:
      ṫ@              remove elements from that right argument numbering the guest value,
        œṡ0           split those remaining around the first zero,
           F          and flatten them back together.
ç@ƒ0œr0    Main link
ç@ƒ0       With the hotel starting as 0, add each guest to the hotel in sequence.
    œr0    Trim trailing zeroes.
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 28 bytes
```
ṫœṡ0F
’⁹ḣ;⁸;ç@ð0ẋ;@
0;ç@/œr0
```
[Try it online!](https://tio.run/nexus/jelly#@/9w5@qjkx/uXGjgxvWoYeajxp0Pdyy2ftS4w/rwcofDGwwe7uq2duAyAPH0j04uMvh/uP1R0xr3//@jDXUUjHUUDGN1FEBMEwhPR8EIJmYQCwA "Jelly – TIO Nexus")
[Answer]
# JavaScript (ES6), ~~144~~ 120 bytes
*Saved 20B thanks to Arnauld and 11B thanks to Neil*
```
a=>a.map((d,c)=>b[d]?(b.splice(d,0,d),b.splice([...b,0].find‌​Index((e,g)=>g&&!e),‌​1)):b[d]=d,b=[])&&[...b].map(c=>c|0)
```
## Usage
You can assign the function to the variable `f` and the list should be given as an array. Example:
```
f=a=>a.map((d,c)=>b[d]?(b.splice(d,0,d),b.splice([...b,0].find‌​Index((e,g)=>g&&!e),‌​1)):b[d]=d,b=[])&&[...b].map(c=>c|0)
f([1,4,3,1,2,1])
```
## Output
The output is in an array as well. Since Javascript works zero-indexed, there is an extra 0 up front.
```
[0, 1, 1, 2, 1, 3, 4]
```
[Answer]
## JavaScript (ES6), 86 bytes
```
f=([n,...a],r=[],p=n,m=r[p],_=r[p]=n)=>n?m?f([m,...a],r,p+1):f(a,r):[...r].map(n=>n|0)
```
Leading zero in the result because JavaScript is 0-indexed.
[Answer]
# Mathematica, 98 bytes
```
Fold[If[Length@#<#2,PadRight@##~Append~#2,Join[Take@##,{#2},Drop@##/.{a___,0,b__}->{a,b}]]&,{0},#]&
```
Unnamed function taking a list of positive integers and returning a 0-indexed list of integers. The whole `If` function takes a partially completed list and the next integer to insert as arguments. If the next integer exceeds the length of the partial list, `PadRight@##~Append~#2` increases the partial list accordingly; otherwise, `Join[Take@##,{#2},Drop@##/.{a___,0,b__}->{a,b}]]` inserts the next integer into its position, then throws away the first `0` found after it. `Fold[...,{0},#]` applies this function repeatedly to the original list, starting with the empty hotel `{0}`, and outputs the final hotel list.
[Answer]
# JavaScript (ES6), 81
Using 0 indexing
```
l=>l.map(v=>(s=(p,v,w=r[p])=>(w&&s(p+1,w),r[p]=v))(v,v),r=[])&&[...r].map(x=>~~x)
```
*Less golfed*
```
l => {
  s = ( // recursively insert a value, shifting present values up until it finds an empty spot
       p, // insert position
       v, // value to insert
       w = r[p] // value a current position
      ) => ( 
         w && s(p+1,w), // if there is a value, put it in the next position
         r[p] = v // now the current place is empty
      );
  r = []; // initialize the result array   
  l.map( // execute the following for each value in input
     v => s(v,v) // insert value
  );
  return [...r].map(x=>~~x) // fill the missing places with 0
}
```
**Test**
```
F=
l=>l.map(v=>(s=(p,v,w=r[p])=>(w&&s(p+1,w),r[p]=v))(v,v),r=[])&&[...r].map(x=>~~x)
out=x=>O.textContent+=x+'\n'
out([1,3,1]+' -> '+F([1,3,1]))
out([10]+' -> '+F([10]))
function go() {
   var v = I.value.match(/\d+/g).map(x=>+x)
   out(v +' -> ' + F(v))
}
go()
```
```
<input id=I value='1 4 3 1 2 1'><button onclick='go()'>go</button>
<pre id=O></pre>
```
[Answer]
# R, 133 bytes
```
a=scan()
z=rep(0,max(a))
for(i in a){b=match(0,z[-1:-i])+i
if(z[i])z[i:b]=c(i,z[i:(b-1)])else(z[i]=i)
z=c(z,0)}
z[1:max(which(z!=0))]
```
To avoid problems with bad indexing, I pad with some zeros, and then strip them at the end. This is maybe not the best solution, but it works.
[Answer]
## Python, ~~134~~ ~~125~~ 116 bytes
```
def a(b):
 r=[]
 i=0
 for n in b:
    d=n
    while n:
     if i<d:r.extend([0]*(d-i));i=d
     n,r[d-1]=r[d-1],n;d+=1
 return r
```
Valid for both Python 2.7.13 and 3.6.0. This code functions by means of a swapping the held value with the value contained at each index until the held value is 0. If it reaches an index not yet in the array, it adds zeros to the end of the array until the array contains that index. Thanks to Wheat Wizard and xnor for golfing off 9 bytes each
]