Count Rate-Limited Requests

You are given a non-decreasing array timestamps of request times in whole seconds. Requests are processed in order and a request is dropped if accepting it would exceed any of these limits:

• at most 3 requests within any 1-second window,
• at most 20 requests within any 10-second window,
• at most 60 requests within any 60-second window.

A window of W seconds ending at a request at time t contains every request with timestamp in [t - W + 1, t], including requests that were dropped, and the request itself.

Return the number of dropped requests.

Examples

Example 1

Input: timestamps = [1,1,1,1,2]
Output: 1
Explanation: The fourth request is the fourth one in second 1, so it is dropped. The fifth request's 1-second window [2,2] holds only itself.

Example 2

Input: timestamps = [0,0,0,0,0,10]
Output: 2
Explanation: The 4th and 5th requests are the 4th and 5th in second 0, so both are dropped. The request at 10 has the window [1,10], which holds only itself.

Example 3

Input: timestamps = [0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6]
Output: 1
Explanation: Three requests per second never break the 1-second limit, but the last request is the 21st inside its 10-second window [-3,6], so it is dropped.