设计一个数据结构，实现LRU Cache的功能(Least Recently Used – 最近最少使用缓存)。它支持如下2个操作： get 和 put。 int get(int key) – 如果key已存在，则返回key对应的值value（始终大于0）；如果key不存在，则返回-1。 void put(int key, int value) – 如果key不存在，将value插入；如果key已存在，则使用value替换原先已经存在的值。如果容量达到了限制，LRU Cache需要在插入新元素之前，将最近最少使用的元素删除。 请特别注意“使用”的定义：新插入或获取key视为被使用一次；而将已经存在的值替换更新，不算被使用。 限制：请在O(1)的时间复杂度内完成上述2个操作。

输入描述:

第一行读入一个整数n，表示LRU Cache的容量限制。 从第二行开始一直到文件末尾，每1行代表1个操作。如果每行的第1个字符是p，则该字符后面会跟随2个整数，表示put操作的key和value。如果每行的第1个字符是g，则该字符后面会跟随1个整数，表示get操作的key。

输出描述:

按照输入中get操作出现的顺序，按行输出get操作的返回结果。