http://paiza.jp/poh/ec-campaign/result/1eb631ed1199db1885e09f8b8656fd47

gistfile1.pl

use strict;
use warnings;

my $PRICE_MAX = 1_000_000;

my @lines = split "\n", do { local $/; <> };
my ( $num_products, undef ) = split( " ", shift(@lines) );
my @prices = splice( @lines, 0, $num_products );

my @hist;
map { $hist[$_]++ } @prices;

my @sorted;
my $sorted_max = 0;

DAY: for my $target ( @lines ) {
    my $best = 0;
    my $idx = 0;
    my $last_val = 0;
    my $search_range = $PRICE_MAX;
    HEAD: while (1) {
        my $val = $sorted[$idx];
        unless ( $val ) {
            do { $sorted_max++ } while !$hist[$sorted_max] && $sorted_max < $PRICE_MAX;
            last HEAD if $sorted_max == $PRICE_MAX;
            $val = $sorted[$idx] = $sorted_max;
        }

        my $tail_target = $target - $val;
        last HEAD if $tail_target < $val;
        TAIL: for my $gap ( 0..$search_range ) {
            if ( $hist[$tail_target - $gap] ) {
                if ( $tail_target - $gap != $val || $hist[$val] > 1 ) {
                    $best = $target - $gap;
                    last HEAD unless $gap;
                    $search_range = $gap - 1;
                    last TAIL;
                }
            }
        }
        $idx++;
    }
    print "$best\n";
}