#define DEBUG

#ifdef DEBUG
#include <stdio.h>
#endif // DEBUG

template<typename T, bool C(T, T)>
class PriorityQue {
public:
	PriorityQue() : PriorityQue(0) {}
	PriorityQue(int n) : size(0), maxSize(n) {
		heap = new T[maxSize];
	}
	~PriorityQue() {
		printf("destructor!\n");
		delete[] heap;
	}
	void push(T value) {
		if (size + 1 > maxSize) return;
		heap[size] = value;
		unsigned int current = size;
		unsigned int parent = (size - 1) >> 1;

		while (current > 0 && C(heap[current], heap[parent])) {
			swap(heap[current], heap[parent]);
			current = parent;
			parent = (current - 1) >> 1;
		}
		size++;
	}
	T pop() {
		if (size < 1) return nullptr;
		T result = heap[0];
		size--;

		heap[0] = heap[size];
		unsigned int current = 0;
		unsigned int left = (current << 1) + 1;
		unsigned int right = (current << 1) + 2;
		unsigned int max = current;

		while (left < size) {
			if (!C(heap[size], heap[left])) {
				max = left;
			}
			if (right < size && !C(heap[max], heap[right])) {
				max = right;
			}
			if (max == current) {
				break;
			}
			else {
				swap(heap[current], heap[max]);
				current = max;
				left = (current << 1) + 1;
				right = (current << 1) + 2;
			}
		}

		return result;
	}

	T first() {
		return size > 0 ? heap[0] : nullptr;
	}
private:
	T* heap = nullptr;
	unsigned int size;
	unsigned int maxSize;
	void swap(T &a, T &b) {
		T tmp = a;
		a = b;
		b = tmp;
	}
};

struct STUDENT {
	int id;
	int score;
};

static int count;
static STUDENT datas[50000];

bool comp_asc(STUDENT* a, STUDENT* b) {
	//return a->score == b->score ? a->id > b->id : a->score > b->score;
	return a->score >= b->score;
}
bool comp_desc(STUDENT* a, STUDENT* b) {
	//return a->score == b->score ? a->id < b->id : a->score < b->score;
	return a->score <= b->score;
}


static PriorityQue<STUDENT*, comp_asc> max_que;
static PriorityQue<STUDENT*, comp_desc> min_que;
static PriorityQue<STUDENT*, comp_desc> mid_high_que;
static PriorityQue<STUDENT*, comp_desc> mid_low_que;

void init(int N, STUDENT students[]) {
	count = N;

	max_que = PriorityQue<STUDENT*, comp_asc>(count);
	min_que = PriorityQue<STUDENT*, comp_desc>(count);
	mid_high_que = PriorityQue<STUDENT*, comp_desc>(count);
	mid_low_que = PriorityQue<STUDENT*, comp_desc>(count);


	for (int i = 0; i < count; i++) {
		datas[i] = students[i];

		max_que.push(&datas[i]);
		min_que.push(&datas[i]);
		STUDENT *mh = mid_high_que.first();
		if (mh != nullptr && comp_asc(&datas[i], mh)) {
			mid_low_que.push(mid_high_que.pop());
		}
		mid_high_que.push(&datas[i]);

#ifdef DEBUG
		printf("[%d: %d] ", datas[i].id, datas[i].score);
#endif // DEBUG
	}
#ifdef DEBUG
	printf("\n");
#endif // DEBUG

#ifdef DEBUG
	printf("max      => %d: %d\n", max_que.first()->id, max_que.first()->score);
	printf("min      => %d: %d\n", min_que.first()->id, min_que.first()->score);
	printf("mid high => %d: %d\n", mid_high_que.first()->id, mid_high_que.first()->score);
	printf("mid low  => %d: %d\n", mid_low_que.first()->id, mid_low_que.first()->score);
#endif
}

void addStudent(STUDENT student) {
}

int removeStudents(int K) {
	return 0;
}

void getSum(int sum[]) {
}