Blue is the next element we must insert, red is searching for this insertion position.