// Всплески пользовательской активности

// Поддерживаем окно событий за 5 минут и словарь user_id -> count .
// При очередном событии выкидываем из окна все старые события и добавляем новое, попутно обновляем словарь.
// Держим счётчик, который учитывает число пользователей с большими запросами


class UserStatistics {
    private var windowLen: Int
    private var limit: Int
    private var userCountOverLimit: Int
    private var events: [(time: Int, userId: Int)]
    private var userEventsCounter: [Int: Int]

    init(k: Int, limit: Int) {
        windowLen = k
        limit = limit
        userCountOverLimit = 0
        events = []
        userEventsCounter = [Int: Int]()
    }

    func removeOldEvents(time: Int) {
        while !events.isEmpty {
            let event = events.first!
            if time - event.time < windowLen {
                break
            }
            events.removeFirst()
            let count = userEventsCounter[event.userId]!
            userEventsCounter[event.userId] = count - 1
            if count == limit {
                userCountOverLimit -= 1
            }
            if userEventsCounter[event.userId] == 0 {
                userEventsCounter.removeValue(forKey: event.userId)
            }
        }
    }

    func event(time: Int, userId: Int) {
        removeOldEvents(time: time)
        events.append((time: time, userId: userId))
        userEventsCounter[userId, default: 0] += 1
        if userEventsCounter[userId] == limit {
            userCountOverLimit += 1
        }
    }

    func robotCount(time: Int) -> Int {
        removeOldEvents(time: time)
        return userCountOverLimit
    }
}