class LRUCache {
public:
    LRUCache(int capacity) : capacity_(capacity) {}

    int get(int key) {
        if (data_.count(key) == 0) return -1;
        key_to_timestamp_[key] = ++timestamp_;
        timestamp_to_key_pq_.push({ timestamp_, key });
        return data_[key];
    }

    void put(int key, int value) {
        if (data_.count(key) == 0 && data_.size() == capacity_) {
            if (timestamp_to_key_pq_.empty()) return;
            auto to_delete = timestamp_to_key_pq_.top();
            auto key_to_delete = std::get<1>(to_delete);
            timestamp_to_key_pq_.pop();

            while (data_.count(key_to_delete) == 0 || key_to_timestamp_[key_to_delete] != std::get<0>(to_delete)) {
                to_delete = timestamp_to_key_pq_.top();
                key_to_delete = std::get<1>(to_delete);
                timestamp_to_key_pq_.pop();
            }

            data_.erase(key_to_delete);
            key_to_timestamp_.erase(key_to_delete);
        }

        data_[key] = value;
        key_to_timestamp_[key] = ++timestamp_;
        timestamp_to_key_pq_.push({ timestamp_, key });
    }

private:
    int capacity_;
    long long timestamp_{ numeric_limits<long long>::min() };
    unordered_map<int, int> data_;
    unordered_map<int, long long> key_to_timestamp_;

    using QueryData = tuple<long long, int>;
    priority_queue<QueryData, vector<QueryData>, std::greater<QueryData>> timestamp_to_key_pq_;
};