use strict;
use warnings;

my (@arr, @sequence, @result, $p, $node);

@arr = 1..20;
randomize(\@arr);

print "@arr\n";

for (@arr) {
    $p = simplefind(\@sequence, $_);
    $node = {'key' => $_};
    if (!$p) {
        $sequence[1] = $node;
    }
    else {
        $node->{'last'} = $sequence[$p];
        $sequence[$p+1] = $node;
    }
}

$node = $sequence[-1];
while ($node) {
    push @result, $node->{'key'};
    $node = $node->{'last'};
}

print join ' ', reverse @result;

sub simplefind {
    my ($p, $key, $i) = @_;
    for ($i = 1; $i <= $#$p; $i++) {
        last if $key < $p->[$i]{'key'};
    }
    return $i-1;
}

sub randomize {
    my ($p, $size, $swap, $key);
    $p = $_[0];

    $size = $#$p;
    for (0..($size-1)) {
        $swap = int rand($size - $_ + 1) + $_;
        $key = $p->[$_];
        $p->[$_] = $p->[$swap];
        $p->[$swap] = $key;
    }
}