#7Kingdom Battle: Capture the Maximum Number of Villages
Two rival kingdoms are preparing for a battle across a long road represented by the X-axis. Along this road, there are several villages. Each village contains one treasure that can be captured by the kingdom. Multiple villages may exist at the same location. You are given a sorted array villagePositions, where villagePositions[i] represents the location of the i-th village. The kingdom has two armies. Each army can control a continuous stretch of land of length exactly k. An army positioned at [L, R] can capture every village whose position satisfies L ≤ villagePosition ≤ R, where R - L = k. The two armies may control overlapping territories. Your goal is to position the two armies so that the kingdom captures the maximum possible number of villages.
Return the maximum number of villages that can be captured using the two armies.
Important Rules The village positions are given in non-decreasing order. Multiple villages can exist at the same position. Each army controls a segment of length exactly k. A village is captured if it lies inside at least one of the two territories. The two territories may overlap. A village should only be counted once, even if both armies capture it.
Examples
Example 1
Input: n = 7
villagePositions = [1, 1, 2, 2, 3, 3, 5]
k = 2
Output: 7
Explanation: The kingdom can deploy its two armies to these territories: Army 1 → [1, 3] Army 2 → [3, 5] Since each territory has length k = 2: 3 - 1 = 2 5 - 3 = 2 Army 1 captures the villages at: [1, 1, 2, 2, 3, 3] Army 2 captures the villages at: [3, 3, 5] The villages at position 3 are captured by both armies, but they are counted only once. Therefore, all 7 villages are captured.
Example 2
Input: n = 4
villagePositions = [1, 2, 3, 4]
k = 0
Output: 2
Explanation: Since k = 0, each army can control only one exact position. One optimal arrangement is: Army 1 → [3, 3] Army 2 → [4, 4] Army 1 captures the village at position 3. Army 2 captures the village at position 4. Therefore: Maximum villages captured = 2
Constraints
- 1 ≤ n ≤ 10^5
- 1 ≤ villagePositions[i] ≤ 10^9
- 0 ≤ k ≤ 10^9
- villagePositions is sorted in non-decreasing order