using System;
using System.Collections.Generic;
using System.Linq;

namespace NormNumbers
{
    class Program
    {
        private static IEnumerable<int> normalize(int min, IEnumerable<int> arr)
        {
            if (!arr.Any())
            {
                yield break;
            }

            var first = arr.First();
            var normalized = first - min > 1
                ? min + 1
                : first;
            yield return normalized;

            foreach (var el in normalize(normalized, arr.Skip(1)))
                yield return el;
        }

        private static IEnumerable<int> buildTree(IEnumerable<int> arr)
        {
            if (!arr.Any())
                return Enumerable.Empty<int>();

            var min = arr.Min();
            var left = normalize(min, arr.TakeWhile(x => x != min).Reverse());
            var right = normalize(min, arr.SkipWhile(x => x != min).Skip(1));
            return buildTree(left.Reverse()).Concat(new[] { min }).Concat(buildTree(right));
        }

        public static void Main()
        {
            var input = new[] {2, 5, 8, 1, 7, 3, 4, 6, 10, 1, 2, 5};
            var output = buildTree(input);
            Console.WriteLine("Input: {0}", string.Join(", ", input));
            Console.WriteLine("Output: {0}", string.Join(", ", output));
        }
    }
}