import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

public class Main {

    @SafeVarargs
    private static <T> Iterator<T> from(T... array) {
        return Arrays.asList(array).iterator();
    }

    @SafeVarargs
    private static <T> void testSuperIterator(List<T> expected, Comparator<T> comparator, Iterator<T>... iterators) {
        final SuperIterator<T> superIterator = new SuperIterator<T>(Arrays.asList(iterators), comparator);
        final List<T> actual = new ArrayList<>(expected.size());
        while (superIterator.hasNext()) {
            actual.add(superIterator.next());
        }

        if (!actual.equals(expected)) {
            throw new IllegalStateException("Expected: " + expected + "! Actual: " + actual);
        }
        System.out.println(actual);
    }

    private static Comparator<Integer> INTEGER_COMPARATOR = Integer::compareTo;

    @SafeVarargs
    private static void testIntSuperIterator(List<Integer> expected, Iterator<Integer>... iterators) {
        testSuperIterator(expected, INTEGER_COMPARATOR, iterators);
    }

    private static Iterator EMPTY_ITERATOR_INSTANCE = new Iterator() {
        
        @Override
        public boolean hasNext() {
            return false;
        }

        @Override
        public Object next() {
            throw new NoSuchElementException();
        }
    };

    private static <T> Iterator<T> emptyIterator() {
        //noinspection unchecked
        return EMPTY_ITERATOR_INSTANCE;
    }

    static class SuperIterator<T> implements Iterator<T> {

        private final Iterator<T>[] iterators;

        private final Object[] peekedElements;

        private final Comparator<T> comparator;

        public SuperIterator(Collection<Iterator<T>> iterators, Comparator<T> comparator) {
            //noinspection unchecked
            final Iterator<T>[] iteratorsArray = (Iterator<T>[]) iterators.toArray();
            this.iterators = iteratorsArray;
            this.peekedElements = new Object[iteratorsArray.length];
            this.comparator = comparator;
        }

        @Override
        public boolean hasNext() {
            for (Object peekedElement : peekedElements) {
                if (peekedElement != null) {
                    return true;
                }
            }

            final Iterator<T>[] iterators = this.iterators;
            for (int i = 0; i < iterators.length; i++) {
                final Iterator<T> iterator = iterators[i];
                if (iterator != null) {
                    if (iterator.hasNext()) {
                        return true;
                    } else {
                        iterators[i] = null;
                    }
                }
            }

            return false;
        }

        @Override
        public T next() {
            final Iterator<T>[] iterators = this.iterators;
            final Object[] peekedElements = this.peekedElements;

            final int length = iterators.length;
            int minValuePosition = -1;
            T minValue = null;
            for (int i = 0; i < length; i++) {
                //noinspection unchecked
                T peekedElement = (T) peekedElements[i];
                if (peekedElement == null) {
                    final Iterator<T> iterator = iterators[i];
                    if (iterator != null) {
                        if (iterator.hasNext()) {
                            peekedElements[i] = peekedElement = iterator.next();
                        } else {
                            iterators[i] = null;
                        }
                    }
                }
                if (peekedElement != null && (minValuePosition < 0 || comparator.compare(peekedElement, minValue) < 0)) {
                    minValuePosition = i;
                    minValue = peekedElement;
                }
            }

            if (minValuePosition < 0) {
                throw new NoSuchElementException();
            }

            peekedElements[minValuePosition] = null;

            return minValue;
        }
    }

    public static void main(String[] args) {
        testIntSuperIterator(
                Collections.emptyList(),
                emptyIterator()
        );

        testIntSuperIterator(
                Collections.singletonList(1),
                from(1)
        );

        testIntSuperIterator(
                Collections.singletonList(Integer.MIN_VALUE),
                from(Integer.MIN_VALUE)
        );

        testIntSuperIterator(
                Arrays.asList(1, 2, 4, 5),
                from(1, 2, 4, 5)
        );

        testIntSuperIterator(
                Arrays.asList(Integer.MIN_VALUE, 1, 2, 4, 5),
                from(Integer.MIN_VALUE, 1, 2, 4, 5)
        );

        testIntSuperIterator(
                Arrays.asList(1, 2, 4, 5),
                emptyIterator(), from(1, 2, 4, 5)
        );

        testIntSuperIterator(
                Arrays.asList(1, 2, 4, 5),
                from(1, 2, 4, 5), emptyIterator()
        );

        testIntSuperIterator(
                Arrays.asList(Integer.MIN_VALUE, 1, 2, 4, 5),
                emptyIterator(), from(Integer.MIN_VALUE, 1, 2, 4, 5)
        );

        testIntSuperIterator(
                Arrays.asList(Integer.MIN_VALUE, 1, 2, 4, 5),
                from(Integer.MIN_VALUE, 1, 2, 4, 5), emptyIterator()
        );

        testIntSuperIterator(
                Arrays.asList(1, 2, 4, 5),
                from(5), from(4), from(1), from(2)
        );

        testIntSuperIterator(
                Arrays.asList(1, 1, 2, 4, 5),
                from(1, 5), from(4), from(1), from(2)
        );

        testIntSuperIterator(
                Arrays.asList(1, 1, 2, 2, 2, 4, 5),
                from(1, 2, 2, 5), from(4), from(1), from(2)
        );

        testIntSuperIterator(
                Arrays.asList(1, 1, 2, 2, 2, 4, 5, Integer.MAX_VALUE, Integer.MAX_VALUE),
                from(1, 2, 5), from(4, Integer.MAX_VALUE), from(1), from(2, 2, Integer.MAX_VALUE)
        );
    }
}