Radio Tower Coverage Problem Description In ByteLand, there are n cities located along the x axis with the ith city located at (Aj, 0). In ByteLand, there is a telecommunications company that manufactures radio towers. The radio tower has a coverage of d units. More precisely, if the radio tower is placed at point (x, 0), then it provides ser- vice to all cities whose location is within d units from (x, 0); that is, the ith city is covered if |x-Ai| ≤ d. The citizens of ByteLand want to figure out where to place the radio tower so as to provide maximum coverage. To help them with this task, answer the following questions. . If a radio tower is placed inside city i, i.e., at (A;, 0), then how many cities does it cover? · What is the maximum number of cities that a single radio tower can cover? Note that for this question, it is not necessary for the tower to be located at a city. Print the answer to each question in one line. Input The input format is as shown below. n d A1 A2 ... An More precisely, the input consists of two lines: · The first line contains two space-separated integers n, d. · The second line contains n space-separated integers A1, A2, . . . An. It is guaranteed that the city locations are given in increasing order, i.e., A¡ > Ai-1 holds for 1 < < < n. Output Output n + 1 lines, where the ith line contains a single integer, the answer to the ith question. . For 1 ≤ i ≤n, print the number of cities covered by a tower located at (A;, 0). . For i = n + 1, print the maximum number of cities that can be covered by a single radio tower. Please ensure that the last line is ended with a newline character '\n'. Constraints . 1 ≤n≤105 · 1 ≤ d ≤109 . 1 ≤ Ai ≤ 109 and Ai ≥ Ai-1 for i > 1 . The time limit is 1 second for C/C++ and 3 seconds for Python. 1 Test Cases Your program will be evaluated on 5 visible test cases and 5 hidden test cases. Each test case is worth 0.6 points. Sample Input 1: 4 3 13 5 7 Sample Output 1: NM MN+ 2 3 2 4 Sample Explanation The x-coordinates of the cities are A = (1, 3, 5, 7). The radius of coverage is d = 3.The answers to the questions are as follows. . If a tower is placed at (1,0) then it covers all cities whose x coordinates are in the range [-2, 4]. Only the first two towers lie in this range. Hence the answer is 2. . A tower is placed at (3,0) covers all towers except the fourth tower. . A tower is placed at (5, 0) covers all towers except the first tower. . A tower is placed at (7,0) covers the third and fourth towers. . We can cover all four towers by placing a tower at (4,0). Hence the answer is 4. Note that it is not necessary to place the tower at one of the cities. Submission Guideline Write your program in either C, C++ or Python in a single file. Submit the file on Gradescope. The time limit on Gradescope is 1 second for C/C++ and 3 seconds for Python. You can make at most 10 submission attempts.