sub quantile {
        my($n, @a) = @_;
        my($q);
        @a < $n and
                return 9e9999;
        $q = quantile1($n, @a);
        if (1) { # DEBUG check postcondition
                my($nl, $nle);
                $nl = grep { $_ < $q } @a;
                $nle = grep { $_ <= $q } @a;
                $nl < $n && $n <= $nle or
                        die "postcondition failed";
        }
        $q;     
}

sub quantile1 {
        my($n, @a) = @_;
        my($c, $v, @l, @h);
        @a <= 1 and do {
                @a or
                        die "internal error: quantile1 called on empty list, n=" . $n;
                return $a[0];
        };
        $c = @a[rand(@a)];
        for $v (@a) {
                if ($v < $c)
                        { push(@l, $v); }
                elsif ($c < $v)
                        { push(@h, $v); }
        }
        if ($n <= @l) {
                quantile1($n, @l);
        } elsif ($n > @a - @h) {
                quantile1($n - @a + @h, @h);
        } else {
                $c;
        }
}