Получение нового массива с неопределённым размером. Многопоточность

Считаю количество уникальных чисел в массиве. Начал переводить данную задачу на несколько потоков и столкнулся с тем, что должен сохранять элементы в новый массив, но я не знаю его размера, так как генерирую числа рандомно, соответственно количество уникальных элементов всегда разное. Как решить данную проблему?

Код для последовательного выполнения:

using System;
using System.Diagnostics;
 
namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            var stopwatch = new Stopwatch();
            stopwatch.Start();
 
            int er;
 
            int k;
 
            k = 0;
 
            int[] array = new int[10000];
 
            Random rand = new Random();
 
            for (int i = 0; i < 10000; i++)
            {
                array[i] = rand.Next(-1000, 1000);
            }
 
            // Уникальные
            for (int i = 0; i < 10000; i++)
            {
                er = 0;
                for (int j = 0; j < 10000; j++)
                    if ((array[i] == array[j]) & (i != j)) er++;
                if (er == 0) k++;
            }
            Console.WriteLine("Уникальных: " + k);
 
            stopwatch.Stop();
            Console.WriteLine($"Затраченное время: {stopwatch.ElapsedMilliseconds}");
        }
    }
}

Как это должно примерно выглядеть в многопотоке:

using System;
using System.Diagnostics;
using System.Threading;
 
namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            var stopwatch = new Stopwatch();
            stopwatch.Start();
 
            int[] array = new int[10000];
 
            Random rand = new Random();
 
            for (int i = 0; i < 10000; i++)
            {
                array[i] = rand.Next(-100, 100);
            }
 
            ThreadStart first_half = new ThreadStart(delegate () { FirstMas(array); });
            Thread thread = new Thread(first_half);
            thread.Start();
 
            ThreadStart second_half = new ThreadStart(delegate () { SecondMas(array); });
            Thread thread2 = new Thread(second_half);
            thread2.Start();
 
            ThreadStart result = new ThreadStart(delegate () { ThirdMas(array); });
            Thread thread3 = new Thread(result);
            thread3.Start();
 
            Console.WriteLine("Уникальных: " + result);
 
            stopwatch.Stop();
 
            Console.WriteLine($"Затраченное время: {stopwatch.ElapsedMilliseconds}");
        }
 
        static int FirstMas(int[] array)
        {
            int er;
 
            int k;
 
            k = 0;
            
            for (int i = 0; i < 5000; i++)
            {
                er = 0;
                for (int j = 0; j < 10; j++)
                    if ((array[i] == array[j]) & (i != j))
                    {
                        er++;
                        // ... Сохранение в массив уникальности №1
                    }
            }
            return ...
        }
 
        static int SecondMas(int[] array)
        {
            int er;
 
            int k;
 
            k = 0;
 
            for (int i = 5000; i < 10000; i++)
            {
                er = 0;
                for (int j = 5000; j < 10000; j++)
                    if ((array[i] == array[j]) & (i != j))
                    {
                        er++;
                        // ... Сохранение в массив уникальности №2
                    }
            }
            return ...
        }
 
        static int ThirdMas(int[] array)
        {
            // Сравнение двух элементов двух массивов на уникальность и подсчёт данных элементов
            return ...
        }
    }
}

В первом потоке - первая половина массива проверяется на уникальность, во втором потоке - вторая половина.