#include <algorithm>
#include <iostream>
#include <vector>
template <typename T>
void orderedInsert(T & v, typename T::value_type addMe)
{
v.insert(std::lower_bound(std::begin(v), std::end(v), addMe), addMe);
}
typedef std::vector<unsigned> vec;
unsigned waysToTravel(vec::iterator beg, vec::iterator end, unsigned min, unsigned max)
{
vec::iterator lb = std::lower_bound(beg, end, *beg + min); // *lb is the first motel in range for the day.
if (lb == end) // We've reached the end of the journey
return 1;
vec::iterator ub = std::upper_bound(beg, end, *beg + max); // *ub is the first motel that isn't in range for the day.
unsigned count = 0;
while (lb != ub) // for each motel in range, count the ways to travel.
count += waysToTravel(lb++, end, min, max);
return count;
}
int main()
{
vec motels = { 0, 990, 1010, 1970, 2030, 2940, 3060, 3930, 4060, 4970, 5030, 5990, 6010, 7000 };
unsigned minDist;
unsigned maxDist;
unsigned numAdditionalMotels;
std::cin >> minDist >> maxDist >> numAdditionalMotels ;
for (unsigned i = 0; i < numAdditionalMotels; ++i)
{
unsigned motel;
std::cin >> motel;
orderedInsert(motels, motel);
}
std::cout << waysToTravel(std::begin(motels), std::end(motels), minDist, maxDist) << '\n';
}
I2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgoKdGVtcGxhdGUgPHR5cGVuYW1lIFQ+CnZvaWQgb3JkZXJlZEluc2VydChUICYgdiwgdHlwZW5hbWUgVDo6dmFsdWVfdHlwZSBhZGRNZSkKewogICAgdi5pbnNlcnQoc3RkOjpsb3dlcl9ib3VuZChzdGQ6OmJlZ2luKHYpLCBzdGQ6OmVuZCh2KSwgYWRkTWUpLCBhZGRNZSk7Cn0KCnR5cGVkZWYgc3RkOjp2ZWN0b3I8dW5zaWduZWQ+IHZlYzsKCgp1bnNpZ25lZCB3YXlzVG9UcmF2ZWwodmVjOjppdGVyYXRvciBiZWcsIHZlYzo6aXRlcmF0b3IgZW5kLCB1bnNpZ25lZCBtaW4sIHVuc2lnbmVkIG1heCkKewogICAgdmVjOjppdGVyYXRvciBsYiA9IHN0ZDo6bG93ZXJfYm91bmQoYmVnLCBlbmQsICpiZWcgKyBtaW4pOyAgLy8gKmxiIGlzIHRoZSBmaXJzdCBtb3RlbCBpbiByYW5nZSBmb3IgdGhlIGRheS4KCiAgICBpZiAobGIgPT0gZW5kKSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAvLyBXZSd2ZSByZWFjaGVkIHRoZSBlbmQgb2YgdGhlIGpvdXJuZXkKICAgICAgICByZXR1cm4gMTsKCiAgICB2ZWM6Oml0ZXJhdG9yIHViID0gc3RkOjp1cHBlcl9ib3VuZChiZWcsIGVuZCwgKmJlZyArIG1heCk7ICAvLyAqdWIgaXMgdGhlIGZpcnN0IG1vdGVsIHRoYXQgaXNuJ3QgaW4gcmFuZ2UgZm9yIHRoZSBkYXkuCgogICAgdW5zaWduZWQgY291bnQgPSAwOwogICAgd2hpbGUgKGxiICE9IHViKSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgLy8gZm9yIGVhY2ggbW90ZWwgaW4gcmFuZ2UsIGNvdW50IHRoZSB3YXlzIHRvIHRyYXZlbC4KICAgICAgICBjb3VudCArPSB3YXlzVG9UcmF2ZWwobGIrKywgZW5kLCBtaW4sIG1heCk7CgogICAgcmV0dXJuIGNvdW50Owp9CgoKaW50IG1haW4oKQp7CiAgICB2ZWMgbW90ZWxzID0geyAwLCA5OTAsIDEwMTAsIDE5NzAsIDIwMzAsIDI5NDAsIDMwNjAsIDM5MzAsIDQwNjAsIDQ5NzAsIDUwMzAsIDU5OTAsIDYwMTAsIDcwMDAgfTsKCiAgICB1bnNpZ25lZCBtaW5EaXN0OwogICAgdW5zaWduZWQgbWF4RGlzdDsKICAgIHVuc2lnbmVkIG51bUFkZGl0aW9uYWxNb3RlbHM7CiAgICBzdGQ6OmNpbiA+PiBtaW5EaXN0ID4+IG1heERpc3QgPj4gbnVtQWRkaXRpb25hbE1vdGVscyA7CiAgICAKICAgIGZvciAodW5zaWduZWQgaSA9IDA7IGkgPCBudW1BZGRpdGlvbmFsTW90ZWxzOyArK2kpCiAgICB7CiAgICAgICAgdW5zaWduZWQgbW90ZWw7CiAgICAgICAgc3RkOjpjaW4gPj4gbW90ZWw7CiAgICAgICAgb3JkZXJlZEluc2VydChtb3RlbHMsIG1vdGVsKTsKICAgIH0KCiAgICBzdGQ6OmNvdXQgPDwgd2F5c1RvVHJhdmVsKHN0ZDo6YmVnaW4obW90ZWxzKSwgc3RkOjplbmQobW90ZWxzKSwgbWluRGlzdCwgbWF4RGlzdCkgPDwgJ1xuJzsKfQ==