2
put 1 1
put 2 2
get 1
put 3 3
get 2
put 4 4
get 1
get 3
get 4

1
-1
-1
3
4

LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

# 定义双向链表的节点类
class Node:
    def __init__(self, key=0, value=0):
        self.key = key       # 键
        self.value = value   # 值
        self.prev = None     # 前驱节点
        self.next = None     # 后继节点

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}  # 哈希表，存储 key -> Node 的映射
        # 初始化虚拟头尾节点，简化边界条件的处理
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    # 从双向链表中删除指定节点
    def _remove(self, node: Node):
        prev = node.prev
        nxt = node.next
        prev.next = nxt
        nxt.prev = prev

    # 将节点添加到链表头部
    def _add_to_head(self, node: Node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key in self.cache:
            node = self.cache[key]
            # 访问后将节点移动到链表头部，表示最近使用
            self._remove(node)
            self._add_to_head(node)
            return node.value
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            # 如果节点存在，更新其值并移动到头部
            node = self.cache[key]
            node.value = value
            self._remove(node)
            self._add_to_head(node)
        else:
            # 如果节点不存在，创建新节点并添加到头部
            new_node = Node(key, value)
            self.cache[key] = new_node
            self._add_to_head(new_node)
            # 若超过容量限制，则移除尾部节点（最久未使用）
            if len(self.cache) > self.capacity:
                tail_node = self.tail.prev
                self._remove(tail_node)
                del self.cache[tail_node.key]

if __name__ == '__main__':
    import sys
    # 读取所有输入行
    lines = sys.stdin.read().splitlines()
    if not lines:
        exit(0)
    # 第一行为缓存容量
    capacity = int(lines[0].strip())
    lru_cache = LRUCache(capacity)
    # 处理后续每一行操作
    for line in lines[1:]:
        tokens = line.strip().split()
        if not tokens:
            continue
        if tokens[0] == "get":
            key = int(tokens[1])
            print(lru_cache.get(key))
        elif tokens[0] == "put":
            key = int(tokens[1])
            value = int(tokens[2])
            lru_cache.put(key, value)

import java.util.HashMap;
import java.util.Scanner;

// 独立定义的 LRU 缓存实现类
class LRUCache {
    // 定义双向链表节点内部类
    private class Node {
        int key;
        int value;
        Node prev;
        Node next;
        
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    
    private int capacity;                     // 缓存容量
    private HashMap<Integer, Node> cache;     // 哈希表存储 key -> Node 的映射
    private Node head, tail;                  // 使用虚拟头尾节点，简化操作
    
    // 构造方法，初始化容量和虚拟链表节点
    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>();
        head = new Node(0, 0);   // 虚拟头节点
        tail = new Node(0, 0);   // 虚拟尾节点
        head.next = tail;
        tail.prev = head;
    }
    
    // 从链表中移除指定节点
    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    
    // 将节点添加到链表头部（表示最近使用）
    private void addToHead(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }
    
    // 获取 key 对应的值，如果存在则移动节点到头部，否则返回 -1
    public int get(int key) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            remove(node);
            addToHead(node);
            return node.value;
        }
        return -1;
    }
    
    // 插入或更新 key-value 数据，如果超出容量则移除尾部节点
    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            node.value = value;
            remove(node);
            addToHead(node);
        } else {
            Node newNode = new Node(key, value);
            cache.put(key, newNode);
            addToHead(newNode);
            if (cache.size() > capacity) {
                Node tailNode = tail.prev;
                remove(tailNode);
                cache.remove(tailNode.key);
            }
        }
    }
}

// 主类 Main，负责输入输出
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 第一行输入缓存容量
        int capacity = scanner.nextInt();
        scanner.nextLine(); // 消耗换行符
        LRUCache lruCache = new LRUCache(capacity);
        // 处理每一行操作
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine().trim();
            if (line.equals("")) continue;
            String[] parts = line.split(" ");
            if (parts[0].equals("get")) {
                int key = Integer.parseInt(parts[1]);
                System.out.println(lruCache.get(key));
            } else if (parts[0].equals("put")) {
                int key = Integer.parseInt(parts[1]);
                int value = Integer.parseInt(parts[2]);
                lruCache.put(key, value);
            }
        }
        scanner.close();
    }
}

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

// LRUCache 类实现
class LRUCache {
private:
    // 定义双向链表节点结构体
    struct Node {
        int key, value;
        Node* prev;
        Node* next;
        Node(int k, int v): key(k), value(v), prev(nullptr), next(nullptr) {}
    };
    
    int capacity;   // 缓存容量
    unordered_map<int, Node*> cache;  // 哈希表：key -> Node*
    Node* head;     // 虚拟头节点
    Node* tail;     // 虚拟尾节点
    
    // 从链表中移除指定节点
    void remove(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    
    // 将节点添加到链表头部
    void addToHead(Node* node) {
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }
    
public:
    // 构造函数，初始化容量和虚拟节点
    LRUCache(int capacity) : capacity(capacity) {
        head = new Node(0, 0);  // 虚拟头节点
        tail = new Node(0, 0);  // 虚拟尾节点
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
        if (cache.find(key) != cache.end()){
            Node* node = cache[key];
            // 移动节点到头部，标记为最近使用
            remove(node);
            addToHead(node);
            return node->value;
        }
        return -1;
    }
    
    void put(int key, int value) {
        if (cache.find(key) != cache.end()){
            // 如果节点存在，更新值并移动到头部
            Node* node = cache[key];
            node->value = value;
            remove(node);
            addToHead(node);
        } else {
            // 如果节点不存在，创建新节点并添加到头部
            Node* newNode = new Node(key, value);
            cache[key] = newNode;
            addToHead(newNode);
            // 当缓存容量超限，删除尾部节点（最久未使用）
            if (cache.size() > capacity) {
                Node* tailNode = tail->prev;
                remove(tailNode);
                cache.erase(tailNode->key);
                delete tailNode;  // 释放内存
            }
        }
    }
    
    // 析构函数，释放所有节点的内存
    ~LRUCache(){
        Node* current = head;
        while(current != nullptr){
            Node* temp = current;
            current = current->next;
            delete temp;
        }
    }
};

int main() {
    int capacity;
    cin >> capacity;
    LRUCache lruCache(capacity);
    string op;
    // 循环处理输入的每个操作
    while(cin >> op) {
        if(op == "get") {
            int key;
            cin >> key;
            cout << lruCache.get(key) << endl;
        } else if(op == "put") {
            int key, value;
            cin >> key >> value;
            lruCache.put(key, value);
        }
    }
    return 0;
}