Включить число в отсортированную последовательность не нарушив порядок

[1сумрак]

В упорядоченную по возрастанию последовательность из целых
чисел включить заданное число так, чтобы упорядоченность не нарушилась


вот до куда я дошел что добавить ?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace IDZ
{
    class Program
    {
        static void Main()
        {
            Console.Write("Введите размер массива: ");
            int n = int.Parse(Console.ReadLine());
            var array = new int[n];
 
            Console.Write("Введите числа через пробел: ");
            string[] parts = Console.ReadLine().Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
            while (n-- > 0) array[n] = int.Parse(parts[n]);
 
            Console.WriteLine("Результат: ");
            foreach (var x in array.OrderBy(x => x)) Console.WriteLine(x);
            Console.ReadKey();
        }
    }
}