Efficiently insert sequential numbers 1-N and renumber duplicates

I have a table whose primary key is a positive integer:

CREATE TABLE T
(
    ID int PRIMARY KEY CHECK (ID > 0) -- not an IDENTITY column
    -- ... other irrelevant columns...
)

Given a positive integer N, I want to insert N records with the IDs 1–N, inclusive. However, if a record with a particular ID already exists, I want to instead insert the next highest unused ID. For example, with N = 5:

If the table contains...    Then insert...
  (Nothing)                   1,2,3,4,5
  1,2,3                       4,5,6,7,8
  3,6,9,12                    1,2,4,5,7

Here's a naïve way to do this:

DECLARE @N int = 5 -- number of records to insert
DECLARE @ID int = 1 -- next candidate ID
WHILE @N > 0 -- repeat N times
BEGIN
    WHILE EXISTS(SELECT * FROM T WHERE ID = @ID) -- conflicting record?
        SET @ID = @ID + 1
    INSERT T VALUES (@ID)
    SET @ID = @ID + 1
    SET @N = @N - 1
END

But if E is the number of existing records, then in the worst case, this code performs E + N SELECTs and N INSERTs, which is quite inefficient.

Is there a smart way to perform this task with a small number of SELECTs and just one INSERT?