using System;
using System.Collections;
using System.Collections.Generic;
using Cr7Sund_DS;

class Program
{
    public static void Main()
    {
        Solution solution = new Solution();
        Console.WriteLine(solution.NthSuperUglyNumber(345, new int[] { 2, 7, 13, 19 }));

    }

    public class Solution
    {
        class Node : IComparable<Node>
        {
            public int val;
            public int index;
            public readonly int prim;

            public Node(int _val, int _index, int _prim)
            {
                val = _val;
                index = _index;
                prim = _prim;
            }

            public int CompareTo(Node other)
            {
                return val.CompareTo(other.val);
            }
        }

        public int NthSuperUglyNumber(int n, int[] primes)
        {
            if (n < 1 || primes.Length < 1) return 0;

            int[] nums = new int[n];
            nums[0] = 1;
            var minHeap = new MinHeap<Node>(n);
            for (int i = 0; i < primes.Length; i++)
                minHeap.Add(new Node(primes[i], 1, primes[i]));

            for (int i = 1; i < n; i++)
            {
                nums[i] = minHeap.Top().val;
                while (nums[i] == minHeap.Top().val)
                {
                    var min = minHeap.Pop();
                    minHeap.Add(new Node(
                        min.prim * nums[min.index],
                        min.index + 1, min.prim
                    ));
                }
            }

            return nums[n - 1];
        }
    }
}

namespace Cr7Sund_DS
{
    using System.Collections.Generic;
    using System.Collections;
    using System;

    public class MinHeap<T> : Heap<T>
        where T : IComparable<T>
    {
        public MinHeap(int size) : base(size)
        {

        }

        public MinHeap() : base()
        {

        }

        public MinHeap(IEnumerable<T> collection) : base()
        {

        }

        protected override int Compare(T item, T other)
        {
            return other.CompareTo(item);
        }
    }

    public class MaxHeap<T> : Heap<T>
        where T : IComparable<T>
    {
        public MaxHeap(int size) : base(size)
        {

        }

        public MaxHeap() : base()
        {

        }

        public MaxHeap(IEnumerable<T> collection) : base()
        {

        }

        protected override int Compare(T item, T other)
        {
            return item.CompareTo(other);
        }
    }

    public abstract class Heap<T> : IEnumerable<T>, IEnumerable, ICollection<T>, ICollection
    where T : IComparable<T>
    {
        protected T[] _array;
        protected int _lastPos = -1;
        int _defaulCapcity = 4;
        Object _syncRoot;
        static T[] EMPTYARRAY = new T[0];

        public int Count => _lastPos + 1;
        public bool IsReadOnly => false;

        //Be Cautions, it maybe lead to error in multiple threading
        //Did not be testify in real project
        public bool IsSynchronized => true;

        public object SyncRoot
        {
            get
            {
                if (_syncRoot == null)
                {
                    System.Threading.Interlocked.CompareExchange<Object>(
                        ref _syncRoot, new Object(), null);
                }
                return _syncRoot;
            }
        }

        protected abstract int Compare(T item, T other);

        protected Heap() => _array = EMPTYARRAY;

        protected Heap(int size) => _array = new T[size];

        protected Heap(IEnumerable<T> collection)
        {
            if (collection == null)
                throw new NullReferenceException();

            var c = collection as ICollection<T>;
            if (c != null)
            {
                int count = c.Count;
                _array = new T[count];
                c.CopyTo(_array, 0);
                _lastPos = count - 1;
            }
            else
            {
                _array = new T[_defaulCapcity];

                using (var en = collection.GetEnumerator())
                {
                    while (en.MoveNext())
                    {
                        Add(en.Current);
                    }
                }
            }
        }

        public bool Empty() => _lastPos < 0 || _array.Length == 0;

        public T Top() => Empty() ?
        throw new IndexOutOfRangeException() : _array[0];

        bool Full() => _lastPos == _array.Length;

        public void Clear()
        {
            Array.Clear(_array, 0, _array.Length);
            _lastPos = -1;
        }

        //Don't suggested , Cost O(n)time
        public bool Contains(T item)
        {
            if ((Object)item == null) return false;
            for (int i = 0; i < Count; i++)
            {
                if (_array[i].Equals(item))
                {
                    return true;
                }
            }

            return false;
        }

        //implementing ICollection<T>
        public void CopyTo(T[] array, int startIndex = 0)
        {
            if (array == null) throw new NullReferenceException();
            if (Empty()) throw new IndexOutOfRangeException("Empty heap");

            if (startIndex < 0 || startIndex > array.Length)
                throw new IndexOutOfRangeException();

            //it should be out of range excetption
            if (array.Length - startIndex < Count)
                throw new IndexOutOfRangeException("the left capcity should be larger than copying size ");

            Array.Copy(_array, 0, array, startIndex, Count);
        }

        public void CopyTo(Array array, int index)
        {
            _array.CopyTo(array, index);
        }

        public void TrimExcess()
        {
            int threshold = (int)((double)_array.Length * 0.9);
            if (Count < threshold)
            {
                var newarray = new T[Count];
                Array.Copy(_array, 0, newarray, 0, Count);
                _array = newarray;
            }
        }

        public void Add(T item)
        {
            ++_lastPos;
            if (Full())
            {
                var newArray = new T[
                    _array.Length == 0 ? _defaulCapcity : 2 * _array.Length];
                //list should use linq.Clone
                //be careful the size
                Array.Copy(_array, 0, newArray, 0, _lastPos);
                _array = newArray;
            }
            _array[_lastPos] = item;
            TrickleUp();
        }

        public T Remove(int index)
        {
            if (index > _lastPos || Empty()) throw new IndexOutOfRangeException();
            var temp = _array[index];

            Swap(_lastPos--, index);
            int parent = (index - 1) / 2;
            if (parent >= 0 && Compare(_array[index], _array[parent]) > 0)
                TrickleUp(index);
            else
                TrickleDown(index);

            return temp;
        }

        // for implementing ICollection
        public bool Remove(T item)
        {
            if (Empty()) throw new IndexOutOfRangeException();
            if ((Object)item == null) return false;
            for (int i = 0; i <= _lastPos; i++)
            {
                if (_array[i].Equals(item))
                {
                    Remove(i);
                    return true;
                }
            }

            return false;
        }

        #region custom methos
        public T[] ToArray()
        {
            var returnArray = new T[Count];
            CopyTo(returnArray);
            return returnArray;
        }

        //should use linq, so  decided  by yourself
        //-------------------------------
        // public List<T> ToList () {
        //     // return ToArray ().ToList ();
        // }

        #endregion

        #region heap operation

        public void Push(T item)
        {
            Add(item);
        }

        public T Pop()
        {
            if (Empty()) throw new IndexOutOfRangeException("No items left");
            T top = _array[0];
            if (_lastPos == -1) return top;

            Swap(_lastPos--, 0);
            TrickleDown();
            return top;
        }

        public T[] Sort()
        {
            Console.WriteLine("K");
            int goBack = this._lastPos;
            while (this._lastPos >= 0)
            {
                 T val = Pop();
            }
            this._lastPos = goBack;
            return _array;
        }

        protected T[] ReverseSort()
        {
            var queue = new Queue<T>();
            int goBack = this._lastPos;
            while (this._lastPos >= 0)
            {
                 queue.Enqueue(Pop());
            }
            this._lastPos = goBack;

            var newArray = new T[goBack + 1];
            int i = -1;
            while (queue.Count > 0)
            {
                newArray[++i] = queue.Dequeue();
            }

            return newArray;
        }

        public T[] Sort(bool IsReverse = false)
        {
            //change state
            //---------------------
            var resultArray = ReverseSort();
            // Why we need a new Array?
            var returnArray = new T[Count];
            if (IsReverse)
            {
                // 1. avoiding changing the newArray because of reference type
                Array.Copy(resultArray, 0, returnArray, 0, Count);
            }
            else
            {
                // 2. trimming the redundent null elements
                CopyTo(returnArray);
            }
            //go back to keep heap after sort
            //Array.Copy(resultArray, 0, _array, 0, Count);
            _array = resultArray;

            return returnArray;
        }

        void TrickleUp()
        {
            int index = _lastPos;
            while (index > 0)
            {
                int parentIndex = (index - 1) / 2;
                if (Compare(_array[index], _array[parentIndex]) <= 0) break;

                Swap(index, parentIndex);
                index = parentIndex;
            }
        }

        void TrickleUp(int index)
        {
            while (index > 0)
            {
                int parentIndex = (index - 1) / 2;
                if (Compare(_array[index], _array[parentIndex]) <= 0) break;

                Swap(index, parentIndex);
                index = parentIndex;
            }
        }

        void TrickleDown(int index = 0)
        {
            while (index >= 0)
            {
                int leftIndex = (index * 2) + 1;
                int rightIndex = (index * 2) + 2;

                if (leftIndex <= _lastPos)
                {
                    int maxIndex = rightIndex <= _lastPos && Compare(_array[leftIndex], _array[rightIndex]) < 0 ?
                        rightIndex : leftIndex;
                    if (Compare(_array[maxIndex], _array[index]) <= 0) break;
                    Swap(maxIndex, index);
                    index = maxIndex;
                }
                else
                {
                    break;
                }
            }
        }

        //undo deletion if you not trim the arrya before
        void UnDoDelete(int steps)
        {
            steps = Math.Min(steps, _array.Length - Count);
            for (int i = steps; i > 0; i--)
            {
                Add(_array[_lastPos + i]);
            }
        }

        void Swap(int a, int b)
        {
            T temp = _array[a];
            _array[a] = _array[b];
            _array[b] = temp;
        }
        #endregion

        #region IEnumeator
        public IEnumerator<T> GetEnumerator()
        {
            //return ((IEnumerable<T>)_array).GetEnumerator();
            return new Enumerator(this);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            //return _array.GetEnumerator();
            return new Enumerator(this);
        }

        struct Enumerator : IEnumerator<T>,
        IEnumerator
        {
            Heap<T> _heap;
            T _current;
            int _index;

            internal Enumerator(Heap<T> heap)
            {
                _heap = heap;
                _current = default(T);
                _index = -2;
            }

            public T Current
            {
                get
                {
                    //enumNotStarted
                    if (_index == -2) throw new NullReferenceException();
                    //enumEnded
                    if (_index == -1) throw new IndexOutOfRangeException();
                    return _current;
                }
            }

            object IEnumerator.Current => Current;

            public void Dispose() => _index = -1;

            public bool MoveNext()
            {
                bool retVal;
                //first call to enumerator
                if (_index == -2)
                {
                    _index = _heap._lastPos;
                    retVal = (_index >= 0);
                    if (retVal)
                    {
                        _current = _heap._array[_index];
                    }

                    return retVal;
                }
                if (_index == -1) return false;

                retVal = (--_index >= 0);
                if (retVal)
                    _current = _heap._array[_index];
                else
                    _current = default(T);

                return retVal;
            }

            public void Reset()
            {
                _index = -2;
                _current = default(T);
            }
        }

        #endregion

    }

}