using System;

using System.Collections.Generic;

using System.Linq;

public class Program

{

    public static void Main()

    {

        var size = 1000;

        var tries = size * 100;

        var random = new Random();

        var array = Enumerable.Range(0, size).ToArray();

        var histogram = array.ToDictionary(k => k, v => 0);

        for(var i=0; i<tries; i++)

            histogram[Random(array, random)]++;

        foreach(var kv in histogram.OrderBy(kv => kv.Key))

            Console.WriteLine($"{kv.Key,5}: {kv.Value}");

    }

    static T Random<T>(IEnumerable<T> source, Random random)

    {

        using var e = source.GetEnumerator();

        if(!e.MoveNext())

            return default;

        var result = e.Current;

        var count = 1;

        while(e.MoveNext())

        {

            if(random.NextDouble() < 1.0 / ++count)

                result = e.Current;

        }

        return result;

    }

}