my %early = my %late = %HoA; # or map { $_ => 1 } keys %HoA
delete $late{Foo};
delete @early{keys %late};
for my $key (keys %early, keys %late) { ... }