#include <iostream>
#include <set>
#include <queue>
#include <list>
#include <vector>
#include <algorithm>
using namespace std;
//using std::priority_queue;
//using std::set;
//using std::list;
//using std::pair;
int algo = 0;
int gl_time = 0;
//struct Proc{
//	List * prev;
//	List * next;
//	int begin, end_time, size;
//	Proc() {}
//	Proc(List * prev, List * next, int begin, int end_time, int size)
//		: prev(prev), next(next), begin(begin), end_time(end_time), size(size) {}
//};
class Set {
  public:
	int size_, begin_;
	List * it_;
	Set() {}
	//Set(int size, int begin) : size_(size), begin_(begin), it_(NULL) {}
	Set(int size, int begin, List * it = NULL) : size_(size), begin_(begin), it_(it) {}
	bool operator< (const Set & a) {
		if (this->size_ <  a.size_)
			return true;
		else if (this->size_ == a.size_) {
			return this->begin_ < a.begin_;
		} else
			return false;
	}
};
class Queue {
  public:
	int end_time_;
	List * it_;
	Queue() {}
	Queue(int end_time, List * it) : end_time_(end_time), it_(it) {}
	bool operator< (const Queue & a) {
		return this->end_time_ < a.end_time_;
	}
};
class List {
  public:
	List * prev;
	List * next;
	int begin, end_time, size;
	set<Set>::iterator it_;
	List() {}
	List(List * prev, List * next, int begin, int end_time, int size, set<Set>::iterator it)
		: prev(prev), next(next), begin(begin), end_time(end_time), size(size), it_(it) {}
};
set<Set> fr_segment;
priority_queue<Queue> bs_segment;
list<List> ram;
void initialize(int n) {
	//free segment with end_time = - 1
	ram.push_back(List(NULL, NULL, 0, -1, n, fr_segment.end()));
}
void insert(pair<int, int> a) { //size, time
	set<Set>::iterator p = fr_segment.lower_bound(Set(a.first, 0));
	if (p != fr_segment.end()) {
		// жду пока освоболиться достаточно памяти
		//removing busy segment form structures
		gl_time = bs_segment.top().end_time_;
		List * p = bs_segment.top().it_;
		//may try to reduce number of if's?
		//partly intersection of if's
		//must be deleting and new inserting into set
		if (p->prev == NULL && p->next == NULL) {
			p->end_time = -1;
			fr_segment.insert(Set(p->size, p->begin));
		} else if (p->next == NULL) {
			if (p->prev->end_time != -1) {
				p->end_time = -1;
				fr_segment.insert(Set(p->size, p->begin, p));
			} else {
				fr_segment.erase(p->it_);
				fr_segment.erase(p->prev->it_);
				p->prev->end_time = -1;
				p->prev->size += p->size;
				p->prev->next = NULL;
				fr_segment.insert(Set(p->prev->size, p->prev->begin, p->prev));
			}
		} else if (p->prev == NULL) {
			if (p->next->end_time != -1) {
				p->end_time = -1;
				fr_segment.insert(Set(p->size, p->begin, p));
			} else {
				fr_segment.erase(p->next->it_);
				p->next->size += p->size;
				p->next->prev = NULL;
				fr_segment.insert(Set(p->next->size, p->begin, p->next));
			}
		} else {
			if (p->prev->end_time == -1 && p->next->end_time == -1) {
				fr_segment.erase(p->it_);
				fr_segment.erase(p->next->it_);
				fr_segment.erase(p->it_);
				p->prev->size += p->size + p->next->size;
				if (p->next->next != NULL) {
					p->prev->next = p->next->next;
					p->next->next->prev = p->prev;
				} else
					p->prev->next = NULL;
				fr_segment.insert(Set(p->prev->size, p->prev->begin, p->prev));
			} else if(p->prev->end_time == -1 && p->next->end_time != -1) {
				fr_segment.erase(p->prev->it_);
				p->prev->size += p->size;
				p->prev->next = p->next;
				p->next->prev = p->prev;
				fr_segment.insert(Set(p->prev->size, p->prev->begin, p->prev));
			} else if(p->prev->end_time != -1 && p->next->end_time == -1) {
				fr_segment.erase(p->next->it_);
				p->next->prev = p->prev;
				p->next->size += p->size;
				p->next->begin = p->begin;
				p->prev->next = p->next;
			}
		}
		bs_segment.pop();
		insert(a);
		return ;
	} else {
		// insert busy segment into list
		List * ls = *p->it_;
		if (ram.empty()) {
			List * temp = new List(NULL, NULL, 0, a.second + gl_time, a.first, fr_segment.begin());
			ram.push_back(*temp);
			fr_segment.insert(Set(a.first, p->begin_, ram.begin()));
			bs_segment.push(Queue(a.second + gl_time, ram.begin()));
		} else if (ls->prev == NULL) {
			fr_segment.erase(p);
			bs_segment.push(Queue());
			ls->prev = new List(NULL, ls, 0, gl_time + a.second, a.first, fr_segment.begin());
			ls->size-= a.first;
			ls->begin += a.first;
		} else if (ls->next == NULL) {
			fr_segment.erase(p);
			bs_segment.push(Queue());
			ls->next = new List(ls, NULL, 0, gl_time + a.second, ls->, fr_segment.begin());
			ls->size-= a.first;
			ls->begin += a.first;
		} else {

		}
		//magic with priority_queue
		bs_segment.push(Queue(gl_time + a.second, (p->it_)->prev));
		gl_time = bs_segment.top().end_time_;
		// insert into set of fr_segment
		insert(a);
		return ;
	}
}
int main() {
	return 0;
}