Recent Counter

You are given a series of requests arriving at times t (in milliseconds). Your task is to implement a RecentCounter that counts the number of requests received in the last 3000 milliseconds (inclusive) for each incoming request.

Specifically, when a request at time t is received, you should return the number of requests that occurred in the time interval \( [t-3000, t] \). This can be efficiently implemented using a queue (or deque) data structure.

Note: The formula for the window is given by \( [t-3000, t] \), where the number 3000 is fixed.

inputFormat

The first line contains a single integer n, the number of requests.

The next n lines each contain an integer t representing the time (in milliseconds) at which a request is received. It is guaranteed that the times are given in non-decreasing order.

outputFormat

For each request, output on a new line an integer representing the number of requests that occurred in the time interval \( [t-3000, t] \) including the current request.

## sample

4
1
100
3001
3002

1
2
3
3

</p>