while ( ($key, $value) = each %HoA ){

 # Construct the array
 foreach my $nextItem (@{$HoA{$key}}) {
   push @newArr, $nextItem;
 }

 # See if array contains $a
 if (grep {$_ eq $a} @newArr) {
   print "Element '$a' found!\n" ;
 }

}