class LRUCache
{
public:
	struct  Node
	{
		int key;
		int value;
		Node *prev;
		Node *next;
	};

	Node *head;
	Node *tail;
	int size , capacity;
	unordered_map<int , Node*>mapi;
	LRUCache(int capacity)
	{
		this->capacity = capacity;
		head = new Node();
		tail = new Node();
		head->next = tail;
		tail->prev = head;
		size =0;
	}

	Node* insertNode(int k , int v)
	{
		Node*newnode = new Node();
		newnode ->key = k;
		newnode->value=v;
		newnode->prev =head;
		newnode->next = head->next;
		newnode->next->prev = newnode;
		head->next = newnode;
		// // unordered_map<int , Node*>mapi
		// pair<int , int> p(k,v);
		mapi.erase(k);
		mapi[k] = newnode; 
		return newnode;
	}

	void pushtowardsHead(Node * newnode)
	{
		if(head->next == newnode)
			return;
		newnode->prev->next = newnode->next;
		newnode->next->prev = newnode->prev;
		newnode->prev =head;
		newnode->next = head->next;
		newnode->next->prev = newnode;
		head->next = newnode;
	}

	void removeTail()
	{
		Node*newnode = tail ->prev;
		tail->prev = newnode ->prev;
		newnode->prev->next= tail;
		mapi.erase(newnode->key);
	}

	int get(int k)
	{
		if(mapi.find(k) == mapi.end())
			return -1;
		Node* newnode =mapi[k];
		pushtowardsHead(newnode);
		return newnode->value;
	}

	void put(int k ,int v)
	{
		if(mapi.find(k)!=mapi.end())
		{//already present
			Node*newnode = mapi[k];
			newnode->value = v;
			pushtowardsHead(newnode);
			return;
		}

		insertNode(k,v);
		if(size <capacity)
		{
			size++;
			return;
		}
		else
		{
			removeTail();
		}
	}
};