#include <deque>
#include <unordered_map>
#include <algorithm>

template<typename T1, typename T2>
class LRU {
public:
	LRU(size_t num)
		: num(num) {
		if (num == 0)
			throw std::runtime_error("Invalid number of elements in LRU list");
	}

	void Add(const T1& key, const T2& element) {
		MoveTop(key, element);
	}

	const T2* Get(const T1& key) {
		auto indexIt = index.find(key);
		if (indexIt == index.end())
			return nullptr;

		MoveTop(key, indexIt->second->second);
		return &elements.back().second;
	}

private:
	void MoveTop(const T1& key, const T2& element) {
		auto indexIt = index.find(key);
		if (indexIt == index.end()) {
			if (elements.size() >= num) {
				index.erase(elements.front().first);
				elements.pop_front();
			}
		}
		else {
			elements.erase(indexIt->second);
		}

		elements.push_back(std::make_pair(key, element));
		index[key] = --elements.end();
	}

private:
	size_t num;
	using Element = std::pair <T1, T2>;
	using Elements = std::list <Element> ;
	Elements elements;
	std::unordered_map<T1, typename Elements::iterator> index;
};