Problem M
Off-World Records
As humans work toward establishing a permanent presence on other planets and their moons, as well as on our own moon, various sporting bodies are under pressure to rethink the notion of a world record. Traditionally an athlete on Earth sets a new world record in a particular sport by surpassing the previous world record in an official event. For example, in the high jump, a new world record is set by jumping higher than the previous world record height. However, clearly this becomes less meaningful if an athlete jumps higher simply by competing in a high jump event on a planet or moon whose gravity is lower than Earth’s. In light of such considerations, the newly formed Intergalactic Athletics Federation (IAF) has begun debating the criteria for setting an off-world record in each sport it oversees. For the high jump, the IAF has decided that an athlete sets a new off-world record if the height of the athlete’s jump (in an official event) is greater than the sum of the current off-world record and the previous off-world record.
Given all the high jump heights certified by the IAF during a competition year1 in the chronological order in which they occurred, determine how many of these high jump heights set a new off-world record.
Note that the instant a new off-world record is set, it becomes the current off-world record, and the off-world record that was just superseded becomes the previous off-world record.
Input
The first line of input contains three space-separated integers: $n$, the number of high jump heights certified by the IAF during a competition year $(1 \leq n \leq 100)$, $c$, the current off-world record height (i.e., the off-world record immediately prior to start of the competition year), and $p$, the previous off-world record height (i.e., the off-world record immediately before the current off-world record).2 This is followed by $n$ lines, each of which contains a high jump height certified by the IAF during the competition year.3 These heights are in the chronological order in which they occurred, all height values lie in the interval $[1, 10^9]$, and $c > p$.
Output
Output a single integer, the number of new off-world records set during the competition year.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 10 5 20 12 50 |
2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 200 100 300 3000 30000 300000 3000000 |
4 |
Footnotes
- We won’t attempt to explain how an intergalactic “year” is defined by the IAF.
- You might wonder how the very first two off-world high jump records were set. The IAF has been tight-lipped about this, but there are persistent disturbing rumours of nepotism.
- High jump heights are measured in universal distance units (UDUs). For those who are curious, $1\, \mathrm{UDU} = 10^\pi $ angstroms.
