Barn Beacon Sweep

# Barn Beacon Sweep ## Problem Farmer Bessie has just installed a network of beacons in her barn to help locate her cows at night. She has N barns arranged in a straight line, numbered 1 to N. She has placed K beacons at various positions along this line, and each beacon has a fixed illumination radius of R barns. A barn is considered illuminated if it is within distance R of at least one beacon. Specifically, a barn at position p is illuminated by a beacon at position b if the distance |p - b| ≤ R. Given the positions of all K beacons and the illumination radius R, determine how many barns are illuminated by at least one beacon. ## Input The first line contains three integers N, R, and K: the total number of barns, the illumination radius, and the number of beacons. The second line contains K space-separated integers representing the positions of the beacons (0-indexed). ## Output Output a single integer: the total number of barns illuminated by at least one beacon. ## Constraints - 1 ≤ N ≤ 100,000 - 0 ≤ R ≤ 10,000 - 1 ≤ K ≤ N - All beacon positions are distinct and in the range [0, N-1] ## Sample Input ``` 10 1 3 2 6 9 ``` ## Sample Output ``` 8 ``` ## Explanation With 10 barns (indexed 0-9), beacons at positions 2, 6, and 9, and radius 1: - Beacon at position 2 illuminates barns 1, 2, 3 (within distance 1) - Beacon at position 6 illuminates barns 5, 6, 7 (within distance 1) - Beacon at position 9 illuminates barns 8, 9 (within distance 1, barn 10 doesn't exist) The union of illuminated barns is {1, 2, 3, 5, 6, 7, 8, 9}, which totals **8 barns**.