Eldon's Stones

Problem Statement

Eldon's Stones Problem Description A ridge trail has n marked spots numbered 0 to n - 1 , and a single stone rests at each spot. The stone at spot i is worth stones[i] , and a value may be negative, because some stones are a burden to carry. Eldon walks the trail from spot 0 towards spot n - 1 and keeps any stones he likes. The spots he keeps need not be next to each other, but his rule for consecutive keeps is strict: whenever he keeps a stone and later keeps another one further along, the gain in value must cover the distance he walked between them. Written out, if the kept spots are i_0 < i_1 < ... < i_(k-1) , the choice is allowed when stones[i_j] - stones[i_(j-1)] >= i_j - i_(j-1) holds for every j from 1 to k - 1 . Keeping exactly one stone is always allowed, and Eldon must keep at least one. Report the largest total value Eldon can finish the walk with. Input Format The first line contains the integer n . The second line contains n space-separated integers, stones[0]