Problems Base course RU

The bucket's size

A subscriber agrees to receive no more than one alert per I seconds on average but is ready for bursts: the limiter is a token bucket that gains one token every I seconds and starts full. Each alert takes a whole token; if there is none, the alert is lost. What is the smallest bucket for which not a single alert of the whole stream is lost?

The tests include all earthquakes of magnitude 5 or more for 2015–2025 at one, five, twenty and sixty alerts an hour.

Input

The first line holds the number of streams q (1 ≤ q ≤ 10). For each, a line with n and I (1 ≤ n ≤ 2·10⁵, 1 ≤ I ≤ 10⁶) and a line with the moments of the alerts in seconds in non-decreasing order (integers from 0 to 10⁹). The sum of n is at most 3·10⁵.

Output

For each stream, the smallest bucket size (an integer number of tokens).

Examples

Example 1

Input

2
5 10
0 1 2 30 31
3 60
0 0 0

Output

3
3

Example 2

Input

2
4 5
0 5 10 15
10 5
0 1 2 3 4 5 6 7 8 9

Output

1
9

Limits

Time · Python: 3000 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 7 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

Take any consecutive alerts from the i-th to the j-th. How many tokens do they need, and how many can the bucket give them?

2Hint 2

The inequality “needed ≤ available” for all pairs i ≤ j can be rewritten as a difference of two numbers, one depending only on i, the other only on j. The largest such difference is found in one pass.

3The idea

Alerts from the i-th to the j-th need j − i + 1 tokens. A bucket of size b can give during this time at most b (the reserve at moment t_i) plus (t_j − t_i)/I (the refill). Everything passes exactly when for all i ≤ j: j − i + 1 ≤ b + (t_j − t_i)/I. Put a_j = I·j − t_j; then the condition is b ≥ (a_j − a_i)/I + 1. The answer is ⌈D/I⌉ + 1, where D is the largest difference a_j − a_i with i ≤ j: a running minimum of a and one pass.

4Walkthrough

Why “sufficient” holds too, not just “necessary”. Suppose the condition holds but some alert j was lost, the first such. Find the last moment before it when the bucket was full, and the first alert i after that moment. Since then the bucket has never overflowed, so it received exactly b + (t_j − t_i)/I tokens and spent j − i, and still there was not enough for the j-th. So j − i + 1 > b + (t_j − t_i)/I, a contradiction.

In the second example there are ten alerts in ten seconds with a token every five seconds: the bucket must hold 9. The most common wrong answer, “how many alerts come in I seconds”, here 5, forgets that a burst longer than one interval drains the bucket gradually. On the earthquake catalogue at five alerts an hour a bucket of 74 is needed: that is what the burst after the magnitude 8.8 earthquake of July 2025 required, 105 events in a little over six hours, although no more than 38 in any single hour. More about the bucket and its guarantee in the article on rate limiting.

4+Solution

5Complexity

O(n) per stream: one pass with a running minimum.

6Common mistakes

The largest number of alerts in I seconds. It ignores long bursts: the second example.
Trying all pairs i ≤ j. O(n²), tens of billions of pairs on the catalogue.
Rounding. b ≥ D/I + 1 with a non-integer D/I rounds up: ⌈D/I⌉ + 1.
Coinciding moments. Several alerts in the same second need a token each; the formula takes this into account, while “one per second” does not.

Algorithms behind it

SYS Algorithm Rate limiting At most N requests per unit of time: a window, a log, two counters and a token bucket. O(1) per request (the log: O(N)) 2 problems TEC Technique Prefix sums The sum of any segment in O(1) after one pass; the two-dimensional version gives the sum of any rectangle of a picture. O(n) to build, O(1) per query 2 problems