Dropped Requests Rate Limiter

Given a non-decreasing array of request timestamps requestTime in seconds, return the number of requests that must be dropped. A request must be dropped if accepting it would exceed any of these limits: At most 3 requests in any 1-second window; At most 20 requests in any 10-second window; At most 60 requests in any 60-second window. For a request at time t, use inclusive windows [t, t], [t-9, t], and [t-59, t]. Important: dropped requests still count toward subsequent rate-limit checks. Input Line 1: integer n Line 2: n non-decreasing integer timestamps Output Number of dropped requests. Constraints 1 <= n <= 2 * 10^5 0 <= requestTime[i] <= 10^9 Compare a naive and an optimal solution, and analyze complexity. Example Input 4 1 1 1 1 Output 1