CF2152F Triple Attack

Zeus is analyzing a replay of the fight to understand his opponent's attack patterns. The opponent has a special ability: if they land three attacks on a target within a time frame of $ z $ , their third attack becomes a powerful, boosted attack. To outplay his opponent, Zeus should not let his opponent trigger their boosted attack. Let $ Y = \{y_1, y_2, \ldots, y_m\} $ be the multiset of $ m $ timestamps, where each $ y_i $ represents the time when the opponent's attack landed. We call $ Y $ to be safe if for every three timestamps $ \{y_i, y_j, y_k\} $ such that $ 1 \le i < j < k \le m $ , it holds that $ \max(y_i, y_j, y_k) - \min(y_i, y_j, y_k) > z $ , where $ z $ is the duration of the time frame that is given to you as an input. Zeus has a log of $ n $ timestamps, $ x_1, x_2, \ldots, x_n $ , representing when the opponent's attacks landed. The timestamps are sorted in nondecreasing order of occurrence. In other words, $ x_i \le x_{i+1} $ for all $ 1 \le i < n $ . Zeus has $ q $ intervals of interest, denoted as two integers $ 1 \le l \le r \le n $ . For each interval, Zeus wants to find the maximum number of attacks among $ [x_l, x_{l+1}, \ldots, x_r] $ that he could have let through: In other words, Zeus wants to find a maximum size subset of the multiset $ \{x_l, x_{l+1}, \ldots, x_r\} $ such that the subset is safe.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 20\,000 $ ). The description of the test cases follows. The first line contains two integers $ n $ and $ z $ ( $ 1 \le n \le 250\,000 $ , $ 1 \le z \le 10^9 $ ). The second line contains $ n $ integers $ x_1, x_2, \ldots, x_n $ ( $ 1 \le x_i \le 10^9 $ ) — the timestamps of the opponent's attacks. It is guaranteed that the array $ x $ is sorted, i.e., $ x_i \le x_{i+1} $ for all $ 1 \le i < n $ . The third line contains a single integer $ q $ ( $ 1 \le q \le 250\,000 $ ). The next $ q $ lines each contain two integers $ l $ and $ r $ ( $ 1 \le l \le r \le n $ ) — the endpoints of the interval. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 250\,000 $ . It is guaranteed that the sum of $ q $ over all test cases does not exceed $ 250\,000 $ .

For each of the $ q $ queries, print a single integer — the maximum size of a safe subset of attack timestamps in the given interval.

In the first query of the first test case, we consider the timestamps $ \{1, 5, 7, 8, 11, 12\} $ with $ z=10 $ . The subset $ \{1, 5, 12\} $ is safe because its only triplet satisfies $ 12 - 1 = 11 > 10 $ . It's impossible to form a safe subset of size $ 4 $ , hence the answer to this query is $ 3 $ . In the first query of the second test case, we consider the timestamps $ \{1\} $ with $ z=1 $ . The entire set $ \{1\} $ is safe because there are no triplets. Hence the answer to this query is $ 1 $ . In the second query of the second test case, we consider the timestamps $ \{1,1,1,3,3,3\} $ with $ z=1 $ . The subset $ S = \{1,1,3,3\} $ is safe because: - For the triple $ (i,j,k) = (1,2,3) $ , $ \max(1,1,3) - \min(1,1,3) = 2 > 1 $ . - For the triple $ (i,j,k) = (1,2,4) $ , $ \max(1,1,3) - \min(1,1,3) = 2 > 1 $ . - For the triple $ (i,j,k) = (1,3,4) $ , $ \max(1,3,3) - \min(1,3,3) = 2 > 1 $ . - For the triple $ (i,j,k) = (2,3,4) $ , $ \max(1,3,3) - \min(1,3,3) = 2 > 1 $ . It's impossible to form a safe subset of size $ 5 $ , hence the answer to this query is $ 4 $ .