#!/usr/bin/perl
@x = (0, 12, 20, 15, 29, 23, 17, 22, 35, 40, 26, 51, 19);
$n = @x - 1;
for my $i (1..$n){
}
for (my $i = 2; $i <= $n; $i++){
siftup($i);
}
for (my $i = $n; $i >= 2; $i--){
swap(1, $i);
siftdown($i-1);
}
for my $i (1..$n){
}
sub swap{
my($a, $b) = @_;
my $tmp = $x[$a];
$x[$a] = $x[$b];
$x[$b] = $tmp;
}
sub siftup{
my($n) = @_;
my $i = $n;
while ($i > 1) {
last if $x[$p] <= $x[$i];
swap($p, $i);
$i = $p;
}
}
sub siftdown{
my($n) = @_;
my $i = 1;
while (2 * $i <= $n) {
my $c = 2 * $i;
if ($c + 1 <= $n && $x[$c + 1] < $x[$c]) {
$c++;
}
last if $x[$i] <= $x[$c];
swap($i, $c);
$i = $c;
}
}
IyEvdXNyL2Jpbi9wZXJsCgpAeCA9ICgwLCAxMiwgMjAsIDE1LCAyOSwgMjMsIDE3LCAyMiwgMzUsIDQwLCAyNiwgNTEsIDE5KTsKJG4gPSBAeCAtIDE7CmZvciBteSAkaSAoMS4uJG4pewogICAgcHJpbnQgIiR4WyRpXSAiOwp9CnByaW50ICJcbiI7CmZvciAobXkgJGkgPSAyOyAkaSA8PSAkbjsgJGkrKyl7CiAgICBzaWZ0dXAoJGkpOwp9CmZvciAobXkgJGkgPSAkbjsgJGkgPj0gMjsgJGktLSl7CiAgICBzd2FwKDEsICRpKTsKICAgIHNpZnRkb3duKCRpLTEpOwp9CmZvciBteSAkaSAoMS4uJG4pewogICAgcHJpbnQgIiR4WyRpXSAiOwp9CnByaW50ICJcbiI7CgpzdWIgc3dhcHsKICAgIG15KCRhLCAkYikgPSBAXzsKICAgIG15ICR0bXAgPSAkeFskYV07CiAgICAkeFskYV0gPSAkeFskYl07CiAgICAkeFskYl0gPSAkdG1wOwp9CgpzdWIgc2lmdHVwewogICAgbXkoJG4pID0gQF87CiAgICBteSAkaSA9ICRuOwogICAgd2hpbGUgKCRpID4gMSkgewogICAgICAgIG15ICRwID0gaW50KCRpIC8gMik7CiAgICAgICAgbGFzdCBpZiAkeFskcF0gPD0gJHhbJGldOwogICAgICAgIHN3YXAoJHAsICRpKTsKICAgICAgICAkaSA9ICRwOwogICAgfQp9CgpzdWIgc2lmdGRvd257CiAgICBteSgkbikgPSBAXzsKICAgIG15ICRpID0gMTsKICAgIHdoaWxlICgyICogJGkgPD0gJG4pIHsKICAgICAgICBteSAkYyA9IDIgKiAkaTsKICAgICAgICBpZiAoJGMgKyAxIDw9ICRuICYmICR4WyRjICsgMV0gPCAkeFskY10pIHsKICAgICAgICAgICAgJGMrKzsKICAgICAgICB9CiAgICAgICAgbGFzdCBpZiAkeFskaV0gPD0gJHhbJGNdOwogICAgICAgIHN3YXAoJGksICRjKTsKICAgICAgICAkaSA9ICRjOwogICAgfQp9Cg==