CF2207B One Night At Freddy's

[Five Nights at Freddy's 1 Song — The Living Tombstone ](https://www.youtube.com/watch?v=l18A5BOTlzE&t=6s)Let $ n, m, \ell $ be positive integers. You have made the unfortunate decision to work as a night guard at Freddy Fazbear's Pizzeria, where there are $ m $ animatronics numbered $ 1, \ldots, m $ waiting to jumpscare you. The night consists of $ \ell $ seconds, numbered $ 1, \ldots, \ell $ . The $ j $ -th of the $ m $ animatronics has a danger level $ d_j $ , and initially $ d_1 = \ldots = d_m = 0 $ . Every second, the danger level of exactly one animatronic will increase by $ 1 $ , and throughout the night, you are able to observe all values of $ d_j $ at the current time. For example, if $ m = 2 $ , one possible list of danger levels after $ 5 $ seconds is $ [d_1, d_2] = [2, 3] $ . You are not defenseless, however. At each of the $ n $ fixed times $ a_i $ ( $ 1 \leq a_1 \lt \ldots \lt a_n \leq \ell $ ), you can shine your flashlight on exactly one animatronic $ j_i $ of your choice. This occurs immediately after the $ a_i $ -th second and sets its danger level back to zero, i.e. $ d_{j_i} := 0 $ . Note that this choice is made independently for each flashlight use $ a_i $ . Continuing the example from before, if $ a_1 = 5 $ and you choose to flash the second animatronic at that time, the danger levels after $ 5 $ seconds will be $ [d_1, d_2] = [2, 0] $ . Let the overall danger be the maximum danger across all animatronics, i.e. $ \max_{1 \leq j \leq m} d_j $ . You will lose if the overall danger at the end of the night (after $ \ell $ seconds) is greater than $ x $ . Find the minimum value of $ x $ such that regardless of the actions of the animatronics, you can guarantee that overall danger will be less than or equal $ x $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains three integers $ n $ , $ m $ , and $ \ell $ ( $ 1 \leq n, m, \ell \leq 2 \cdot 10^5, n \leq \ell, 1 \leq m \cdot \ell \leq 2 \cdot 10^5 $ ) — the number of flashlight actions, animatronics, and the length of the night, respectively. The next line contains $ n $ integers $ a_i $ ( $ 1 \leq a_1 \lt \ldots \lt a_n \leq \ell $ ) — the times at which you get to shine your flashlight. It is guaranteed that the sum of $ m \cdot \ell $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, output a single integer — the minimum $ x $ such that you can guarantee that your final danger level is at most $ x $ .

In the first test case, there are $ 2 $ animatronics and a night length of $ 10 $ , and you get to flash after the $ 10 $ -th second. We will show that $ x = 5 $ is always possible. After $ 10 $ seconds, notice that one animatronic must have at least $ 5 $ danger, and the other must have at most $ 5 $ danger. So, we can flash the higher one and get a final danger level at most $ 5 $ . It can be shown that $ 5 $ is the minimum possible value of $ x $ . In the second test case, there is only one animatronic and a night length of $ 32 $ . Notice that in this case, the animatronic just increments its danger by $ 1 $ each second. So, after the $ 25 $ -th second, we reset its danger to $ 0 $ . Seven more seconds pass before the night ends, so the final danger we get is always $ 7 $ . In the third test case, it can be proven that the minimum possible value of $ x $ is $ 19 $ .