Design Hit Counter

Design a hit counter which counts the number of hits received in the past 5 minutes (that is, the past 300 seconds).

Implement the HitCounter class:

• HitCounter() Initializes the object of the hit counter system.
• void hit(int timestamp) Records a hit that happened at timestamp (in seconds). Several hits may happen at the same timestamp.
• int getHits(int timestamp) Returns the number of hits in the past 5 minutes from timestamp.

You may assume that calls are made in chronological order, so timestamp is monotonically increasing.

Examples

Example 1:

Input: ["HitCounter","hit","hit","hit","getHits","hit","getHits","getHits"] [[],[1],[2],[3],[4],[300],[300],[301]]

Output: [null,null,null,null,3,null,4,3]

Explanation:

HitCounter hitCounter = new HitCounter(); hitCounter.hit(1); hitCounter.hit(2); hitCounter.hit(3); hitCounter.getHits(4); // return 3 hitCounter.hit(300); hitCounter.getHits(300); // return 4 hitCounter.getHits(301); // return 3

Example 2:

Input: ["HitCounter","hit","hit","hit","getHits","getHits"] [[],[1],[1],[1],[1],[300]]

Output: [null,null,null,null,3,3]

Explanation:

Multiple hits in the same second share the same bucket, but all of them still count within the 300-second window.

Constraints

• 1 <= timestamp <= 2 * 10^9
• timestamp values are passed in non-decreasing order.
• At most 300 calls will be made to hit and getHits.