import java.lang.AutoCloseable;
import java.util.Collection;
import java.util.AbstractQueue;
import java.util.Iterator;
import java.util.TreeSet;
import java.util.HashSet;

import java.util.NoSuchElementException;
import java.util.ConcurrentModificationException;

import static java.lang.Math.max;

/**
 * A maximum priority queue based on an unordered array.
 * Supports fast constant-time insertions of the elements, but
 * the retrieve-max-value methods work only in linear time.
 */
class MaxPQUnorderedArray<T extends Comparable<? super T>>
		extends AbstractQueue<T> {

	private T[] data;

	// Соответствует логическому количеству элементов, когда nOpenedIterators == 0,
	// иначе включает удалённые.
	private int nAll = 0;

	// Множество индексов удалённых элементов. Создаётся по запросу.
	//
	// Удаление i-го индекса инвалидирует хотя бы один из индексов >= i,
	// поэтому finishPostponedRemoves должна иметь возможность обойти
	// удаляемые индексы от старшего к младшему. Так что HashSet не подходит.
	//
	// Вместо TreeSet можно использовать битовое поле из nAll бит,
	// в котором '1' соответствуют удалённым элементам.
	// Такое битовое поле будет эффективнее, когда количество удалённых элементов
	// сравнимо с количеством вообще всех элементов в очереди.
	//
	// Есть смысл сделать ОБА варианта и переключаться с TreeSet на битовое поле
	// в момент достижения чего-то типа removed >= max(24, 4% элементов).
	private TreeSet<Integer> postponedRemoves;

	// Удаления откладываются при nOpenedIterators > 0.
	private int nOpenedIterators = 0;

	public MaxPQUnorderedArray() { }

	/**
	 * Creates a MaxPQ containing the elements from the
	 * specified collection.
	 */
	@SuppressWarnings("unchecked")
	public MaxPQUnorderedArray(Collection<T> elements) {
		addAll(elements);
	}

	/**
	 * Create an empty queue with the specified initial capacity.
	 */
	@SuppressWarnings("unchecked")
	public MaxPQUnorderedArray(int initialCapacity) {
		if (initialCapacity < 0) {
			throw new IllegalStateException(String.format(
				"Expected: initialCapacity >= 0."
				+ " Got: initialCapacity = %d", initialCapacity
			));
		}
		reallocate(initialCapacity);
	}

	/**
	 * Adds an element to the queue.
	 * @return true in case the queue is modified as a result of the call.
	 */
	@Override
	public boolean offer(T value) {
		grow(1);
		data[nAll++] = value;
		return true;
	}

	/**
	 * Adds all of the elements from the specified collection.
	 * @return  true in case every element from the collection has been
	 *		  added to the queue.
	 */
	@Override
	public boolean addAll(Collection<? extends T> elements) {
		int i = nAll;
		grow(elements.size());
		for (T element : elements) {
			data[i++] = element;
		}
		nAll = i;
		return true;
	}

	/**
	 * Retrieves, but does not remove, the max value stored in the queue
	 * or returns {@code null} in case the queue is empty.
	 * This method can be slightly improved by keeping the position
	 * of the max element, so that subsequential calls of {@code element}
	 * or {@code remove} would take constant time instead of linear.
	 */
	@Override
	public T peek() {
		int iMax = findMax();
		return iMax >= 0 ? data[iMax] : null;
	}

	/**
	 * Retrieves and removes the maximum element of the queue or
	 * just retunrls {@code null} in case the queue is empty.
	 */
	@Override
	public T poll() {
		int iMax = findMax();
		if (iMax < 0) return null;
		T max = data[iMax];
		removeAt(iMax);
		return max;
	}

	/**
	 * Removes all elements from the queue.
	 */
	@Override
	@SuppressWarnings("unchecked")
	public void clear() {
		if (nOpenedIterators == 0) {
			nAll = 0;
			shrink();
		} else {
			// Мне лень думать.
			for (int i = 0; i < nAll; i++)
				if (!flyblown(i)) postponeRemoveAt(i);
		}
	}

	@Override
	public boolean isEmpty() {
		return nAll == flyblownCount();
	}

	@Override
	public int size() {
		return nAll - flyblownCount();
	}

	@Override
	public PQIterator iterator() {
		var result = new PQIterator(); // can throw, at least OOM!
		nOpenedIterators++; // so increment only now
		return result;
	}

	int findMax() {
		int iMax = -1;
		for (int i = 0; i < nAll; i++)
			if (!flyblown(i) && (iMax < 0 || data[iMax].compareTo(data[i]) < 0))
				iMax = i;
		return iMax;
	}

	void removeAt(int index) {
		if (nOpenedIterators == 0)
			removeRightAwayAt(index);
		else
			postponeRemoveAt(index);
	}

	void removeRightAwayAt(int index) {
		data[index] = data[nAll - 1];
		nAll--;
		shrink();
	}

	void postponeRemoveAt(int index) {
		assert postponedRemoves == null || !postponedRemoves.contains(index);
		if (postponedRemoves == null) postponedRemoves = new TreeSet<Integer>();
		postponedRemoves.add(index);
	}

	void finishPostponedRemoves() {
		if (postponedRemoves == null) return;
		while (!postponedRemoves.isEmpty())
			removeRightAwayAt(postponedRemoves.pollLast());
	}

	// flyblown == true означает, что элемент удалён и не должен быть виден снаружи.
	// Я хотел сделать нескучное название, но так и не вспомнил, как будет «зашкварен».
	//
	// Проверки nOpenedIterators экономят вызовы .contains и .size у заведомо
	// пустого множества, но портят отладочный вывод в PQIterator.close.
	boolean flyblown(int index) {
		return /* nOpenedIterators > 0 && */ postponedRemoves != null && postponedRemoves.contains(index);
	}

	int flyblownCount() {
		return /*nOpenedIterators == 0 || */ postponedRemoves == null ? 0 : postponedRemoves.size();
	}

	static final int MIN_GROW = 4;
	/**
	 * Reallocates the memory used to store the elements of the queue
	 * in a way to fit next `by` added elements. Grows the length of the
	 * array at least 1.5 times. We call this method beforehand the
	 * actual insertions of the elements, because it allows us to
	 * have fully filled array.
	 */
	private void grow(int by) {
		if (data == null ? by > 0 : nAll + by > data.length) {
			reallocate(nAll + max(by, max(MIN_GROW, data == null ? 0 : data.length / 2)));
		}
	}

	/**
	 * Considers reducing the physical storage size, i. e. 'data'.
	 * Meant to be called after reducing element count.
	 */
	private void shrink() {
		if (data != null && nAll <= data.length / 4) {
			// make the array that would be 50% full
			int newLen = max(MIN_GROW, 2 * nAll);

			// shrink only if this will remove strictly MORE than MIN_GROW cells,
			// so adding and removing a single item into an empty queue won't cause
			// repetitive reallocations.
			if (data.length - newLen > MIN_GROW) {
				reallocate(newLen);
			}
		}
	}

	/**
	 * Changes the size of the array in which the elements are stored.
	 */
	@SuppressWarnings("unchecked")
	private void reallocate(int newSize) {
		assert newSize >= nAll;

		Comparable<?>[] newData = new Comparable<?>[newSize];
		if (data != null) System.arraycopy(data, 0, newData, 0, nAll);
		data = (T[]) newData;
	}

	// Итератор весьма медленный.
	//
	// Можно сделать так: если итератор прошёл уже >=10 элементов —
	// на этот раз не max(10, 4% элементов), а именно 10 или подобная очень маленькая константа —
	// то составить max-кучу из всех оставшихся живых элементов (и их индексов)
	// и в следующих next выдавать элементы из неё.
	//
	// Но это лечение гангрены подорожником. Нормальная реализация — см. в треде.
	private class PQIterator implements Iterator<T>, Iterable<T>, AutoCloseable {
		private HashSet<Integer> seen = new HashSet<Integer>();
		int nAll = MaxPQUnorderedArray.this.nAll;
		int last = -1;
		int cachedNext = -1; // speed up hasNext() + next() sequence.

		public PQIterator() { }

		public boolean hasNext() {
			return findNext(true) >= 0;
		}

		public T next() {
			int iNext = findNext(false);
			if (iNext < 0) throw new NoSuchElementException("The queue is empty");
			last = iNext;
			seen.add(iNext);
			return data[iNext];
		}

		public void remove() {
			if (last < 0) throw new IllegalStateException("Iterator doesn't point to an item.");
			postponeRemoveAt(last);
			last = -1;
		}

		private int findNext(boolean isHasNextCheck) {
			int iMax = cachedNext;
			if (iMax < 0) {
				for (int i = 0; i < nAll; i++)
					if (!seen.contains(i) && !flyblown(i) && (iMax < 0 || data[iMax].compareTo(data[i]) < 0))
						iMax = i;
			}
			cachedNext = isHasNextCheck ? iMax : -1; // сохранить в hasNext(), сбросить в next().
			return iMax;
		}

		@Override
		public void close() {
			if (seen == null) return; // я не знаю, предосторожность от двойного close().
			seen = null;
			if (--nOpenedIterators == 0) {
				System.out.printf("\nlast iterator closed, flyblownCount = %d\n", flyblownCount());
				finishPostponedRemoves();
			}
		}

		@Override
		public PQIterator iterator() { return this; }
	}

	public static void main(String[] args) {
		MaxPQUnorderedArray<Integer> pq = new MaxPQUnorderedArray<>();
		for (int i = 0; i < 10; i++) {
			pq.add(i);
		}
		try (var iterator = pq.iterator()) {
			while (iterator.hasNext()) {
				int next = iterator.next();
				System.out.printf("%d ", next);
				if (next == 5 || next == 2 || next == 3) {
					iterator.remove();
				}
			}
		}

		System.out.println();
		try (var iterator = pq.iterator()) {
			for (int i : iterator) {
				System.out.printf("%d ", i);
			}
		}
	}
}