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++];
	}
};

dGVtcGxhdGU8Y2xhc3MgSXRlbT4KY2xhc3MgUFF7CnByaXZhdGU6CglJdGVtICpwcTsJCS8q0JzQsNGB0YHQuNCyINGN0LvQtdC80LXQvdGC0L7QsiovCglpbnQgbjsJCQkvKtCi0LXQutGD0YnQtdC1INC+0LvQuNGH0LXRgdGC0LLQviDRjdC70LXQvNC10L3RgtC+0LIg0LIg0L7Rh9C10YDQtdC00LgqLwoJaW50IG1heDsJCS8q0JzQsNC60YHQuNC80LDQu9GM0L3QvtC1INC60L7Qu9C40YfQtdGB0YLQstC+INGN0LvQtdC80LXQvdGC0L7QsiDQsiDQvtGH0LXRgNC10LTQuCovCglpbnQgbWluX2VsZW07CS8q0JjQvdC00LXQutGBINC80LjQvdC40LzQsNC70YzQvdC+0LPQviDRjdC70LXQvNC10L3RgtCwINCyINC+0YLRgdC+0YDRgtC40YDQvtCy0LDQvdC90L7QvCDQvNCw0YHRgdC40LLQtSovCnB1YmxpYzoKCVBRKGludCBtYXgpewoJCXBxID0gbmV3IEl0ZW1bbWF4XTsKCQluID0gMDsKCQl0aGlzLT5tYXggPSBtYXg7CgkJLyrQotC+0LvRjNC60L4g0LTQu9GPINCy0LXRgNGB0LjQuCDQvdCwINC+0YHQvdC+0LLQtSDQvtGC0YHQvtGA0YLQuNGA0L7QstCw0L3QvdC+0LPQviDQvNCw0YHRgdC40LLQsDoqLwoJCW1pbl9lbGVtID0gMDsKCX0KCgl+UFEoKXsKCQlkZWxldGVbXSBwcTsKCX0KCglpbnQgZW1wdHkoKSBjb25zdHsgcmV0dXJuIG4gPT0gMDsgfQoKCS8q0KTRg9C90LrRhtC40Y8g0LTQvtCx0LDQstC70LXQvdC40Y8g0Y3Qu9C10LzQtdC90YLQsCwg0L/QvtC00LTQtdGA0LbQuNCy0LDRjtGJ0LDRjyDRg9C/0L7RgNGP0LTQvtGH0LXQvdC90L7RgdGC0Ywg0LzQsNGB0YHQuNCy0LAqLwoJdm9pZCBpbnNlcnQoSXRlbSBpdGVtKXsKCQlpZihuKzEgPD0gbWF4KXsKCQkJaW50IGxvY2F0aW9uID0gbiAtIDE7CgoJCQl3aGlsZShsb2NhdGlvbiA+PSAwICYmIHBxW2xvY2F0aW9uXSA+IGl0ZW0pewoJCQkJcHFbbG9jYXRpb24gKyAxXSA9IHBxW2xvY2F0aW9uXTsKCQkJCWxvY2F0aW9uID0gbG9jYXRpb24gLSAxOwoJCQl9CgkJCXBxW2xvY2F0aW9uICsgMV0gPSBpdGVtOwoJCQluKys7CgkJfQoJCS8vcHFbbisrXSA9IGl0ZW07Cgl9CgoJLypJdGVtIGdldG1heCgpewoJCWludCBtYXggPSAwOwoKCQlmb3IoaW50IGkgPSAxOyBpIDwgbjsgaSsrKQoJCQlpZihwcVttYXhdIDwgcHFbaV0pCgkJCQltYXggPSBpOwoJCXN0ZDo6c3dhcChwcVttYXhdLCBwcVtuLTFdKTsKCQlyZXR1cm4gcHFbLS1uXTsKCX0KCglJdGVtIGdldG1pbigpewoJCWludCBtaW4gPSAwOwoKCQlmb3IoaW50IGkgPSAxOyBpIDwgbjsgaSsrKQoJCQlpZihwcVttaW5dID4gcHFbaV0pCgkJCQltaW4gPSBpOwoJCXN0ZDo6c3dhcChwcVttaW5dLCBwcVtuLTFdKTsKCQlyZXR1cm4gcHFbLS1uXTsKCX0qLwoKCS8q0KDQtdCw0LvQuNC30LDRhtC40Y8g0YTRg9C90LrRhtC40LkgZ2V0bWF4INC4IGdldG1pbiDQtNC70Y8g0L7Rh9C10YDQtdC00LgsINC60L7RgtC+0YDQsNGPINGD0L/QvtGA0Y/QtNC+0YfQuNCy0LDQtdGCINGB0LLQvtC5INC80LDRgdGB0LjQsiovCglJdGVtIGdldG1heCgpewoJCXJldHVybiBwcVstLW5dOwoJfQoKCUl0ZW0gZ2V0bWluKCl7CgkJcmV0dXJuIHBxW21pbl9lbGVtKytdOwoJfQp9Ow==