using System;
using System.Collections.Generic;
using System.Linq;
 
namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            var arr = Enumerable.Range(1, 1000).ToArray();
 
            for (int i = 0; i < 100; i++)
            {
                var element = arr.GetRandomSample(1).Single();
                Console.WriteLine(element);
            }
        }
    }
 
    public static class X
    {
        private static readonly Random Random = new Random(1);
        public static IEnumerable<T> GetRandomSample<T>(this IReadOnlyCollection<T> source, int maxCount)
        {
            var numbersPicked = 0;
            int i = 0;
            foreach (var number in source)
            {
                var prob = (maxCount - numbersPicked) / (double)(source.Count - i);
                if (Random.NextDouble() <= prob)
                {
                    yield return number;
                    numbersPicked++;
                }
                i++;
            }
        }
    }
}
 

dXNpbmcgU3lzdGVtOwp1c2luZyBTeXN0ZW0uQ29sbGVjdGlvbnMuR2VuZXJpYzsKdXNpbmcgU3lzdGVtLkxpbnE7CgpuYW1lc3BhY2UgQ29uc29sZUFwcGxpY2F0aW9uMgp7CiAgICBjbGFzcyBQcm9ncmFtCiAgICB7CiAgICAgICAgc3RhdGljIHZvaWQgTWFpbihzdHJpbmdbXSBhcmdzKQogICAgICAgIHsKICAgICAgICAgICAgdmFyIGFyciA9IEVudW1lcmFibGUuUmFuZ2UoMSwgMTAwMCkuVG9BcnJheSgpOwoKICAgICAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCAxMDA7IGkrKykKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgdmFyIGVsZW1lbnQgPSBhcnIuR2V0UmFuZG9tU2FtcGxlKDEpLlNpbmdsZSgpOwogICAgICAgICAgICAgICAgQ29uc29sZS5Xcml0ZUxpbmUoZWxlbWVudCk7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CgogICAgcHVibGljIHN0YXRpYyBjbGFzcyBYCiAgICB7CiAgICAgICAgcHJpdmF0ZSBzdGF0aWMgcmVhZG9ubHkgUmFuZG9tIFJhbmRvbSA9IG5ldyBSYW5kb20oMSk7CiAgICAgICAgcHVibGljIHN0YXRpYyBJRW51bWVyYWJsZTxUPiBHZXRSYW5kb21TYW1wbGU8VD4odGhpcyBJUmVhZE9ubHlDb2xsZWN0aW9uPFQ+IHNvdXJjZSwgaW50IG1heENvdW50KQogICAgICAgIHsKICAgICAgICAgICAgdmFyIG51bWJlcnNQaWNrZWQgPSAwOwogICAgICAgICAgICBpbnQgaSA9IDA7CiAgICAgICAgICAgIGZvcmVhY2ggKHZhciBudW1iZXIgaW4gc291cmNlKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICB2YXIgcHJvYiA9IChtYXhDb3VudCAtIG51bWJlcnNQaWNrZWQpIC8gKGRvdWJsZSkoc291cmNlLkNvdW50IC0gaSk7CiAgICAgICAgICAgICAgICBpZiAoUmFuZG9tLk5leHREb3VibGUoKSA8PSBwcm9iKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIHlpZWxkIHJldHVybiBudW1iZXI7CiAgICAgICAgICAgICAgICAgICAgbnVtYmVyc1BpY2tlZCsrOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgaSsrOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQp9Cg==