import java.util.*;

class PrioK?<T extends Comparable<T>> implements K?<T>, Iterable<T> {

    private Node<T> f?rste = null;
    private int st?rrelse = 0;

    private static class Node<T> {

        T element;
        Node<T> neste;

        public Node(T element) {
            this.element = element;
            this.neste = null;
        }
    }

    @Override
    public boolean erTom() {
        return st?rrelse == 0;
    }

    @Override
    public int st?rrelse() {
        return st?rrelse;
    }

    @Override
    public T hvemErNeste() {
        if (erTom()) {
            return null;
        }
        return f?rste.element;
    }

    @Override
    public void inn(T element) {
        Node<T> ny = new Node<>(element);
        st?rrelse++;
        // Hvis k?en er tom eller h?yest prioritet
        if (f?rste == null || element.compareTo(f?rste.element) < 0) {
            ny.neste = f?rste;
            f?rste = ny;
            return;
        }
        // Finn plass etter prioritet
        Node<T> s?ker = f?rste;
        while (
            s?ker.neste != null && element.compareTo(s?ker.neste.element) >= 0
        ) {
            s?ker = s?ker.neste;
        }
        // Funnet plassen
        ny.neste = s?ker.neste;
        s?ker.neste = ny;
    }

    @Override
    public T ut() {
        if (erTom()) {
            return null;
        }
        T element = f?rste.element;
        f?rste = f?rste.neste;
        st?rrelse--;
        return element;
    }

    @Override
    public Iterator<T> iterator() {
        return new K?Iterator();
    }

    private class K?Iterator implements Iterator<T> {

        private Node<T> gjeldende = f?rste;

        @Override
        public boolean hasNext() {
            return gjeldende != null;
        }

        @Override
        public T next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            T element = gjeldende.element;
            gjeldende = gjeldende.neste;
            return element;
        }
    }
}