Attack from the rear:

splice( @array, $_, 1) for (reverse sort @remindexes);

This way, you start with the highest array index and move down, so you don't have to keep count of how many elements you have removed.