Angry Cows (Bronze)#10593
Bessie the cow has designed what she thinks will be the next big hit video game: "Angry Cows". The premise, which she believes is completely original, is that the player launches a cow with a slingshot into a one-dimensional scene consisting of a set of hay bales located at various points on a number line. The cow lands on a hay bale with enough force to cause it to explode, which in turn may set off a chain reaction causing additional nearby hay bales to explode. The goal is to use a single cow to start a chain reaction that detonates as many hay bales as possible.
There are hay bales located at distinct integer positions x_1, x_2, \ldots, x_n on the number line. If a cow is launched onto a hay bale at position , that hay bale explodes with a "blast radius" of , meaning that any other hay bales within unit of distance are also engulfed by the explosion. These neighboring bales then explode themselves (all simultaneously), each with a blast radius of , so their explosions may engulf additional hay bales up to units away. In the next time step, these bales also explode (all simultaneously) with a blast radius of . In general, at time , a set of hay bales will explode, each with a blast radius of . Any bales engulfed by these explosions will themselves explode at time t + 1 with a blast radius of t + 1, and so on.
Please determine the maximum number of hay bales that can explode if a single cow is launched onto the best possible hay bale to start the chain reaction.
The first line contains an integer n~(1 \le n \le 100. The next lines each contain an integer x_i~(0 \le x_i \le 10^9), specifying the position of one hay bale on the number line.
Print the maximum number of hay bales that a single cow can cause to explode.
In this example, launching a cow onto the hay bale at position will cause the bales at positions and to explode, each with a blast radius of . These explosions, in turn, cause the bales at positions and to explode, each with a blast radius of . However, these final explosions are not strong enough to reach the bale at position .
Example 1