#include <bits/stdc++.h>
using namespace std;

struct Value
{
    Value(int count_, int time_, int key_, int value_)
        : count(count_),
          key(key_),
          value(value_),
          time(time_) {}
    bool operator<(const Value &a) const
    {
        return count == a.count ? time < a.time : count < a.count;
    }
    int key;
    int value;
    int count;
    int time;
};
class LFUCache
{
public:
    LFUCache(int capacity_)
        : capacity(capacity_),
          time(0) {}

    int get(int key)
    {
        if (capacity == 0)
            return -1;
        auto it = table.find(key);
        if (it == table.end())
            return -1;
        Value cache = it->second;
        judge.erase(cache);
        cache.count++;
        cache.time = ++time;
        judge.insert(cache);
        it->second = cache;
        return cache.value;
    }

    void put(int key, int value)
    {
        if (capacity == 0)
            return;
        auto it = table.find(key);
        if (it == table.end())
        {
            if (table.size() == capacity)
            {

                table.erase(judge.begin()->key);
                judge.erase(judge.begin());
            }
            Value put_(0, ++time, key, value);
            table.insert({key, put_});
            judge.insert(put_);
        }
        else
        {
            Value temp = it->second;
            judge.erase(temp);
            Value put_(++temp.count, ++time, key, value);
            it->second = put_;
            judge.insert(put_);
        }
    }

private:
    const int capacity;
    int time;
    unordered_map<int, Value> table;
    set<Value> judge;
};