A chain of n signal beacons is strung along a coastline, numbered 1 through n in the order they stand. Each beacon broadcasts at a fixed strength. A survey team wants to flag every "leading beacon": beacon i is a leading beacon if, among only two specific neighbors — the beacon exactly k positions earlier in the chain and the beacon exactly k positions later in the chain — its own strength is strictly greater than each of those two neighbors that actually exists inside the chain. If a beacon has neither of those neighbors within the chain (they would fall off either end), it counts as a leading beacon automatically. Compute the sum of the strengths of every leading beacon in the chain.
A single integer: the sum of the strengths of all leading beacons.
Example 1
Input
5 2 1 2 3 4 5
Expected
9
Explanation
Chain (1-indexed): 1,2,3,4,5 with k=2. Beacon 1 has no k-earlier neighbor and its k-later neighbor is beacon 3 (strength 3); since 1 is not greater than 3, beacon 1 fails. Beacon 2 similarly fails against beacon 4. Beacon 3 beats its earlier neighbor (beacon 1, strength 1) but loses to its later neighbor (beacon 5, strength 5), so it fails. Beacon 4 (strength 4) only needs to beat its earlier neighbor, beacon 2 (strength 2) — it does, and it has no later neighbor (4+2=6>5), so beacon 4 is leading. Beacon 5 (strength 5) only needs to beat its earlier neighbor, beacon 3 (strength 3) — it does, and it has no later neighbor. So beacons 4 and 5 are the leading beacons, and the answer is 4+5=9.
Example 2
Input
1 1 7
Expected
7
Explanation
With only one beacon and k=1, there is no beacon 1-k=0 or 1+k=2 within the chain, so both checks are vacuously satisfied and the single beacon counts as leading by default. The answer is its strength, 7.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →