# Maintain a parallel min-stack. Each push records the current minimum.
# When you pop the main stack, pop the min-stack too.
# min[-1] is always the minimum of everything currently in the stack.

class MinStack:
    def __init__(self):
        self.stack = []
        self.mins  = []

    def push(self, val):
        self.stack.append(val)
        current_min = min(val, self.mins[-1]) if self.mins else val
        self.mins.append(current_min)

    def pop(self):
        self.stack.pop()
        self.mins.pop()

    def top(self):
        return self.stack[-1]

    def getMin(self):
        return self.mins[-1]

# Stack + max-heap. Problem: popping from one structure doesn't remove from the other.
# Solution: lazy deletion — track deleted indices; skip them on access.

import heapq

class MaxStack:
    def __init__(self):
        self.stack   = []          # (value, index)
        self.heap    = []          # (-value, -index) — max-heap via negation
        self.deleted = set()       # indices that have been logically deleted
        self.index   = 0

    def push(self, x):
        self.stack.append((x, self.index))
        heapq.heappush(self.heap, (-x, -self.index))
        self.index += 1

    def _clean_stack(self):
        while self.stack and self.stack[-1][1] in self.deleted:
            self.stack.pop()

    def _clean_heap(self):
        while self.heap and -self.heap[0][1] in self.deleted:
            heapq.heappop(self.heap)

    def pop(self):
        self._clean_stack()
        val, idx = self.stack.pop()
        self.deleted.add(idx)
        return val

    def top(self):
        self._clean_stack()
        return self.stack[-1][0]

    def peekMax(self):
        self._clean_heap()
        return -self.heap[0][0]

    def popMax(self):
        self._clean_heap()
        val, neg_idx = heapq.heappop(self.heap)
        self.deleted.add(-neg_idx)
        return -val

# Version 1 — queue (simple, memory grows with hit rate)
from collections import deque

class HitCounter_Queue:
    def __init__(self):
        self.que = deque()

    def hit(self, timestamp):
        self.que.append(timestamp)

    def getHits(self, timestamp):
        while self.que and timestamp - self.que[0] >= 300:
            self.que.popleft()
        return len(self.que)


# Version 2 — circular array (O(300) constant space regardless of hit rate)
# Key: slot = timestamp % 300. If the stored timestamp matches, increment.
# If not, it's from a previous cycle — reset the slot.

class HitCounter_Circular:
    def __init__(self):
        self.counts = [0] * 300   # hit count per slot
        self.times  = [0] * 300   # which timestamp owns this slot

    def hit(self, timestamp):
        slot = timestamp % 300
        if self.times[slot] == timestamp:
            self.counts[slot] += 1
        else:
            self.times[slot]  = timestamp
            self.counts[slot] = 1

    def getHits(self, timestamp):
        total = 0
        for i in range(300):
            if timestamp - self.times[i] < 300:
                total += self.counts[i]
        return total

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cap   = capacity
        self.cache = OrderedDict()   # insertion-order dict with O(1) move_to_end

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)  # mark as recently used
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)   # evict least recently used (front)

# dict alone can't getRandom in O(1) — no index-based access.
# Combine: dict maps value → list index; list holds values.
# Delete trick: swap target with last element, then pop last.

import random

class RandomizedSet:
    def __init__(self):
        self.val_to_idx = {}
        self.vals       = []

    def insert(self, val):
        if val in self.val_to_idx:
            return False
        self.val_to_idx[val] = len(self.vals)
        self.vals.append(val)
        return True

    def remove(self, val):
        if val not in self.val_to_idx:
            return False
        idx  = self.val_to_idx[val]
        last = self.vals[-1]

        self.vals[idx]          = last     # overwrite target with last
        self.val_to_idx[last]   = idx      # update last's index
        self.vals.pop()
        del self.val_to_idx[val]
        return True

    def getRandom(self):
        return random.choice(self.vals)

# MinStack  → parallel min-stack, O(1) all ops
# MaxStack  → stack + heap + lazy deletion, O(log n) popMax
# Deque max → monotonic deque for sliding window max (see sliding-window note)

# Pattern: when a heap and a stack conflict on deletions,
# use a "deleted" set for lazy cleanup — skip on next access.