DMPG '15 B5 - Lux-urious S'mores

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 0.6s
Memory limit: 64M

Problem type

After beating his friends at their card game, Bob decides to make a few s'mores before retiring for the night. Bob loves s'mores, so he decides to build N campfires arranged neatly in a circle to roast his s'mores quickly. Unfortunately, he does not know how efficient each of the fires are, and it is here that he requires your help.

Each campfire x burns with a certain intensity I_x. The variance of a campfire V_x is the larger of the absolute values of the difference in intensity between itself and either of the two adjacent fires, calculated as \max(|I_x - I_{x-1}|, |I_{x+1} - I_x|).

Little does he know that campfires must fulfill exactly one of two conditions to be able to cook s'mores as efficiently as possible.

  • I_x \ge K — its intensity should be at least K degrees, otherwise the s'mores will not melt fast enough.
  • V_x \le L — its variance should be at most L degrees, since similar fires will cook the s'mores evenly.

Input Specification

The input begins with three space-separated integers on one line N (3 \le N \le 500); K, L (0 \le K, L \le 500), representing the number of campfires Bob absentmindedly built, the minimum recommended intensity, and the maximum recommended variance respectively.

The next N lines will each contain a single integer I_i (1 \le I_i \le 500), denoting the intensity of the i^{th} campfire, in the order in which Bob has arranged them.

Output Specification

Output a single integer, denoting the number of campfires Bob has built that can be used to cook s'mores efficiently.

Sample Input

3 2 1

Sample Output



There are no comments at the moment.