This smells like a good homework problem.

At the risk of it being such, I'll answer anyway.

I'd copy the array into a new array, picking out the initial number of each item, but inserting any items that weren't there.

my @newarray;
for (@array) {
  my ($prefix) = /^(\d+)/ or die "Missing leading integer in $_\n";
  ## generate missing elements based on length of @newarray:
  push @newarray, (@newarray + 1) . ".lost"
    while @newarray < $prefix - 1;
  push @newarray, $_;
}
@array = @newarray; # copy the results back
[download]

-- Randal L. Schwartz, Perl hacker
Be sure to read my standard disclaimer if this is a reply.