using System;

using System.Collections.Generic;

using System.ComponentModel.DataAnnotations;

using System.Linq;

using System.Net;

using System.IO;

using System.Runtime.CompilerServices;

using System.Text.RegularExpressions;

​

public class Program

{

    public static void Main()

    {

​

        using (WebClient client = new WebClient())

        {

            var inputString = client.DownloadString(@"http://tiskotown.org/input10.txt");

            var nums = inputString.Split("\r\n").Select(x => int.Parse(x)).OrderBy(x => x).ToList();

            nums.Insert(0,0);

            nums.Add(nums.Last()+3);

            var i=0;

            var canBeRemoved = new List<int>();

​

            while (i < nums.Count()-1)

            {

                var diff1 = nums[i+1]-nums[i];

                var diff2 = nums[(i + 2 < nums.Count() - 1) ? (i + 2) : (i + 1)] - nums[i + 1];

                //Console.WriteLine($"i: {i} high: {nums[i+1]} low: {nums[i]} diff: {diff}");

                if (diff1 == 1 && diff2==1)

                {

                    canBeRemoved.Add(nums[i+1]);

                }

​

                i++;

​

            }

​

​

            var removableCombinations = new List<List<int>>();

​

            //var muki = 0;

            var combinationLength = canBeRemoved.Count;

            while (combinationLength > 0)

            {

                //muki = 0;

                Console.WriteLine(combinationLength);

                GenerateCombination(new List<int>(), 0, combinationLength);

                combinationLength--;

            }

​

            Console.WriteLine(removableCombinations.Count(IsValid) + 1);

​

            void GenerateCombination(List<int> combination, int index, int len)

            {

                //Console.WriteLine(muki++);

                //if(combination is null) combination = new List<int>();

                if (len == 0) {

                    removableCombinations.Add(combination.ToList());

                    return;

                }

​

                // start from next index till last index

                for (int j = index; j < canBeRemoved.Count; j++)

                {

                    var list = new List<int>();

                        list.AddRange(combination.ToList());

                        list.Add(canBeRemoved[j]);

​

                    GenerateCombination(list, j + 1, len - 1);

                }

​

            }

​

            bool IsValid(List<int> testable)

            {

                var copy = nums.ToList();

                var removed = copy.Except(testable).ToList();

                var isValid = removed.All(x =>

                {

                    var ind = removed.IndexOf(x);

                    if (ind < removed.Count-1 && (removed[ind + 1] - removed[ind] > 3)) return false;

                    return true;

                });

​

​

                return isValid;

            }

            string validRegEx(string pattern, string input)

            {

                var regEx = new Regex(pattern);

​

                var matches = regEx.Matches(input);

​

                return matches.Any() ? matches[0].Value : null;

            }

​

        }

​

    }

}