Puts a key/value pair into the array, optimizing for the case where the key is greater than all existing keys in the array.