Well, not sure where your code goes awry (though it doesn't seem like checking the last 2, er 3 (length -2) array entries would keep the array unique - 41 is appearing as element 4 and 20) but how about a hash? Something like:

while ( scalar keys %qs  < $Max - 1 ) {
  $qs{int(rand($lines))}++;
}
[download]

a