C#, гонки на подах, ускорить выполнение кода

[POrro]

Мой код проходит первые тесты, но потом на вход идет 100000+ чисел и время превышает максимальное в 1 сек, как можно его ускорить?
Задание:
Гонки на подах популярный вид развлечений. Удовольствие от них способны получить и участники, и зрители, и букмекерские конторы, принимающие ставки на результат очередной гонки. При этом владельцы букмекерских контор периодически совершают некоторые незаконные действия, чтобы повлиять на итоговые позиции гонщиков. Например, можно испортить тормозную систему в некоторых подах, после чего гонщику придется ехать существенно медленнее обычной скорости ради сохранения контроля гонщика над машиной.

Выяснилось, что в последней гонке участвовали n гонщиков. У каждого из гонщиков на машине был написан номер — число от 1 до n, номера всех гонщиков различались. Также известно, что владельцы одной из букмекерских контор испортили тормозную систему во всех машинах, номера которых превосходили некоторое число k. Любая машина с испорченной тормозной системой будет ехать медленнее, чем любая машина с исправными тормозами. Соответственно, в протоколе с результатами гонки у любой машины с номером большим, чем k, место будет также больше, чем k.

Вы проводите расследование этого неприятного инцидента. В качестве первого шага расследования вы решили найти все возможные значения числа k, изучая только результаты гонки.

Формат ввода:
В первой строке входного файла содержится одно целое число n (1 ≤ n ≤ 100 000) — количество гонщиков, участвовавших в соревновании. Вторая строка содержит n различных чисел ai (1 ≤ ai ≤ n) — протокол с результатами гонки, где ai — номер машины, которая заняла i-ое место.

Формат вывода:
В первой строке выходного файла выведите одно целое число c — количество возможных значений числа k. В следующей строке выведите c натуральных чисел, разделенных пробелами — возможные значения числа k. Все числа во второй строке должны быть различны и не должны превосходить n. Числа во второй строке должны быть упорядочены по возрастанию.

private static void Main(string[] args)
        {
            int length = int.Parse(Console.ReadLine());
            string[] strArray = Console.ReadLine().Split(" ".ToCharArray(), StringSplitOptions.RemoveEmptyEntries);
            int[] numArray = new int[length];
            for (int index = 0; index < length; ++index)
                numArray[index] = int.Parse(strArray[index]);
            List<int> intList = new List<int>();
            for (int index1 = 0; index1 < length; ++index1)
            {
                int index2 = 0;
                while (index2 < index1 && numArray[index2] <= numArray[index1])
                    ++index2;
                if (index2 == index1)
                {
                    int num1 = 0;
                    int num2 = 0;
                    int index3;
                    for (index3 = index1 + 1; index3 < length; ++index3)
                    {
                        if (numArray[index3] > numArray[index1])
                            num1 = index3;
                        else
                            num2 = index3;
                        if (num1 > 0 && num2 > 0 && num1 < num2)
                            break;
                    }
                    if (index3 == length)
                        intList.Add(numArray[index1]);
                }
            }
            intList.Sort();
            Console.WriteLine(intList.Count);
            for (int index = 0; index < intList.Count; ++index)
            {
                Console.Write(intList[index]);
                if (index + 1 < intList.Count)
                    Console.Write(" ");
            }
        }

[BDA]

У вас сложность получилась O(N^2), если не путаю. Чтобы ускорить нахождение ответа, нужно упростить алгоритм. Особо не тестировал:

List<int> intList = new List<int>();
int k = 1;
for (int index = 0; index < length; ++index)
{
    if (numArray[index] > k)
        k = numArray[index];
    if (k - 1 <= index)
        intList.Add(k);
}
Console.WriteLine(intList.Count);
for (int index = 0; index < intList.Count - 1; ++index)
{
    Console.Write(intList[index]);
    Console.Write(" ");
}
Console.Write(intList[intList.Count - 1]);

[POrro]

BDA, Спасибо, помогло