Вставка новой фамилии после заданной так, чтобы алфавитный порядок не нарушился

#include <iostream>
#include <windows.h>
#include <conio.h>
#include <string>
using namespace std;
 
void main()
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    int const SIZE = 5;
    string arr[SIZE] = { "Иван", "Денис", "Пётр", "Александр", "Валерий" };
    string key;
 
    cout << "Имена в изначальном порядке: " << endl;
    for (int i = 0; i < SIZE; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
 
    for (int i = 0; i < SIZE; i++)
    {
        string key = arr[i];
        int j = i - 1;
 
        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            arr[j] = key;
            j--;
        }
    }
    cout << "\nИмена, отсортированные в алфавитном порядке: " << endl;
    for (int i = 0; i < SIZE; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
 
        bool flag = false;
        int l = 0; 
        int r = 5;
        int mid;
 
        cout << endl << "Введите слово: ";
        cin >> key; 
 
        while ((l <= r) && (flag != true))
        {
            mid = (l + r) / 2; 
 
            if (arr[mid] == key)
                flag = true; 
 
            if (arr[mid] > key)
                r = mid - 1; 
 
            else l = mid + 1;
        }
 
        if (flag) cout << "\nИндекс имени " << key << " в массиве равен: " << mid;
        else
        {
            cout << "\nТакого имени в массиве нет\n";
            int const SIZE = 6;
            string arr[SIZE] = { "Иван", "Денис", "Пётр", "Александр", "Валерий", key };
            string key;
 
            for (int i = 0; i < SIZE; i++)
            {
                string key = arr[i];
                int j = i - 1;
 
                while (j >= 0 && arr[j] > key)
                {
                    arr[j + 1] = arr[j];
                    arr[j] = key;
                    j--;
                }
            }
            cout << "\nМассив с добавленным новым именем, отсортированным в алфавитном порядке: " << endl;
            for (int i = 0; i < SIZE; i++)
            {
                cout << arr[i] << " ";
            }
            cout << endl;
 
        }
 
    _getch();
}