template<class Item>
class PQ{
private:
	Item *pq;		/*Массив элементов*/
	int n;			/*Текущее оличество элементов в очереди*/
	int max;		/*Максимальное количество элементов в очереди*/
	int min_elem;	/*Индекс минимального элемента в отсортированном массиве*/
public:
	PQ(int max){
		pq = new Item[max];
		n = 0;
		this->max = max;
		/*Только для версии на основе отсортированного массива:*/
		min_elem = 0;
	}

	~PQ(){
		delete[] pq;
	}

	int empty() const{ return n == 0; }

	/*Функция добавления элемента, поддерживающая упорядоченность массива*/
	void insert(Item item){
		if(n+1 <= max){
			int location = n - 1;

			while(location >= 0 && pq[location] > item){
				pq[location + 1] = pq[location];
				location = location - 1;
			}
			pq[location + 1] = item;
			n++;
		}
		//pq[n++] = item;
	}

	/*Item getmax(){
		int max = 0;

		for(int i = 1; i < n; i++)
			if(pq[max] < pq[i])
				max = i;
		std::swap(pq[max], pq[n-1]);
		return pq[--n];
	}

	Item getmin(){
		int min = 0;

		for(int i = 1; i < n; i++)
			if(pq[min] > pq[i])
				min = i;
		std::swap(pq[min], pq[n-1]);
		return pq[--n];
	}*/

	/*Реализация функций getmax и getmin для очереди, которая упорядочивает свой массив*/
	Item getmax(){
		return pq[--n];
	}

	Item getmin(){
		return pq[min_elem++];
	}
};