#include #include #include #include #include #include #include #include namespace emthrm { template struct SparseTable { using BinOp = std::function; SparseTable() = default; explicit SparseTable(const std::vector& a, const BinOp bin_op) { init(a, bin_op); } void init(const std::vector& a, const BinOp bin_op_) { bin_op = bin_op_; const int n = a.size(); assert(n > 0); lg.assign(n + 1, 0); for (int i = 2; i <= n; ++i) { lg[i] = lg[i >> 1] + 1; } const int table_h = std::countr_zero(std::bit_floor(a.size())) + 1; data.assign(table_h, std::vector(n)); std::copy(a.begin(), a.end(), data.front().begin()); for (int i = 1; i < table_h; ++i) { for (int j = 0; j + (1 << i) <= n; ++j) { data[i][j] = bin_op(data[i - 1][j], data[i - 1][j + (1 << (i - 1))]); } } } Band query(const int left, const int right) const { assert(left < right); const int h = lg[right - left]; return bin_op(data[h][left], data[h][right - (1 << h)]); } private: BinOp bin_op; std::vector lg; std::vector> data; }; } // namespace emthrm // #910622 ベース int main() { constexpr int kMaxN = 5000, kMinA = -1000000000, kMaxA = 1000000000; int n, l, r; std::cin >> n >> l >> r; assert(1 <= n && n <= kMaxN && kMinA <= l && l <= r && r <= kMaxA); std::vector a(n); for (int i = 0; i < n; ++i) { std::cin >> a[i]; assert(kMinA <= a[i] && a[i] <= kMaxA); } std::ranges::sort(a); std::vector p_prime(n, n), q(n, -1), q_prime(n); for (int i = 0; i < n; ++i) { for (int lb = -1; lb + 1 < p_prime[i];) { const int p = std::midpoint(lb, p_prime[i]); (a[i] * a[p] >= l ? p_prime[i] : lb) = p; } for (int ub = n; q[i] + 1 < ub;) { const int cand_q = std::midpoint(q[i], ub); (a[i] * a[cand_q] <= r ? q[i] : ub) = cand_q; } if (q[i] < p_prime[i]) { p_prime[i] = n; q[i] = -1; } else { p_prime[i] = std::max(p_prime[i], i + 1); } q_prime[i] = std::min(q[i], i - 1); } int ans = 1; const emthrm::SparseTable sparse_table( q_prime, [](const int x, const int y) -> int { return std::max(x, y); }); for (int i = 0; i < n; ++i) { if (p_prime[i] <= q[i]) { const int f = 3 - p_prime[i] + sparse_table.query(p_prime[i], q[i] + 1); ans = std::max({ans, f, 2}); } } std::cout << ans << '\n'; return 0; }