Design and implement a data structure for a **least frequently used (LFU) cache**. Implement a class `LFUCache` with the following operations: - `LFUCache(int capacity)` — initializes the cache with a positive integer `capacity`. - `int get(int key)` — returns the value associated with `key` if it exists in the cache; otherwise returns `-1`. - `void put(int key, int value)` — if `key` already exists, updates its value. Otherwise, inserts the key–value pair. If inserting the new pair would exceed `capacity`, the cache must first **evict the least frequently used key**. If two or more keys are tied for the lowest use frequency, evict the **least recently used** key among them. **Frequency rules:** - A key's use counter is set to `1` when it is inserted with `put`. - Every subsequent `get` or `put` on an existing key increments its use counter by `1`. - When a key is evicted and later re-inserted, its counter starts again at `1`. Both `get` and `put` must run in **O(1)** average time complexity. **Example:** ``` LFUCache cache = new LFUCache(2); cache.put(1, 10); // cache = {1: 10}, freq(1) = 1 cache.put(2, 20); // cache = {1: 10, 2: 20}, freq(1) = 1, freq(2) = 1 cache.get(1); // returns 10; freq(1) = 2 cache.put(3, 30); // capacity full: key 2 has the lowest frequency, so evict 2 // cache = {1: 10, 3: 30}, freq(3) = 1 cache.get(2); // returns -1 (evicted) cache.get(3); // returns 30; freq(3) = 2 cache.put(4, 40); // keys 1 and 3 are tied at frequency 2; key 1 is the // least recently used of the two, so evict 1 // cache = {3: 30, 4: 40} cache.get(1); // returns -1 (evicted) cache.get(3); // returns 30 cache.get(4); // returns 40 ``` **Constraints:** - `1 <= capacity <= 10^4` - `0 <= key <= 10^5` - `0 <= value <= 10^9` - At most `2 * 10^5` total calls will be made to `get` and `put`.