;; -*- coding: utf-8 -*-
(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0)))
  #+swank (progn (ql:quickload '(:cl-debug-print :fiveam))
                 (shadow :run)
                 (use-package :fiveam))
  #-swank (set-dispatch-macro-character #\# #\> (lambda (s c p) (declare (ignore c p)) (read s nil (values) t))))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)

;; BEGIN_INSERTED_CONTENTS
;;;
;;; Compute binomial coefficient by direct bignum arithmetic
;;;
;;; This code ist almost the same as that of alexandria.
;;;

(declaim (inline %multiply-range))
(defun %multiply-range (i j)
  (labels ((bisect (j k)
             (declare (type (integer 1 #.most-positive-fixnum) j k)
                      (values integer))
             (if (< (- k j) 8)
                 (multiply-range j k)
                 (let ((middle (+ j (truncate (- k j) 2))))
                   (* (bisect j middle)
                      (bisect (+ middle 1) k)))))
           (multiply-range (j k)
             (declare (type (integer 1 #.most-positive-fixnum) j k))
             (do ((f k (* f m))
                  (m (1- k) (1- m)))
                 ((< m j) f)
               (declare (type (integer 0 (#.most-positive-fixnum)) m)
                        (type unsigned-byte f)))))
    (bisect i j)))

(declaim (inline factorial))
(defun factorial (n)
  (%multiply-range 1 n))

(defun binomial-coefficient (n k)
  (declare #.OPT
           ((integer 0 (#.most-positive-fixnum)) n k))
  (assert (>= n k))
  (if (or (zerop k) (= n k))
      1
      (let ((n-k (- n k)))
        (when (< k n-k)
          (rotatef k n-k))
        (if (= 1 n-k)
            n
            (floor (%multiply-range (+ k 1) n)
	           (%multiply-range 1 n-k))))))

(defun multiset-coefficient (n k)
  (binomial-coefficient (+ n k -1) k))

(defmacro dbg (&rest forms)
  #+swank
  (if (= (length forms) 1)
      `(format *error-output* "~A => ~A~%" ',(car forms) ,(car forms))
      `(format *error-output* "~A => ~A~%" ',forms `(,,@forms)))
  #-swank (declare (ignore forms)))

(defmacro define-int-types (&rest bits)
  `(progn
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))) bits)
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))) bits)))
(define-int-types 2 4 7 8 15 16 31 32 62 63 64)

(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
  (let ((*read-default-float-format* 'double-float))
    (prog1 (princ obj stream) (terpri stream))))

(defconstant +mod+ 1000000007)

;; Body

(defun main ()
  (declare #.OPT)
  (let* ((n (read))
         (a (read))
         (b (read))
         (vs (sort (make-array n :element-type 'uint62 :initial-contents (the list (loop repeat n collect (read)))) #'>))
         (max-score (loop for end from a to b maximize (/ (loop for i below end sum (aref vs i) of-type uint62) end)))
         (prevs (make-array n :element-type 'uint32 :initial-element 1)))
    (declare (uint8 n a b))
    (println (float max-score 1d0))
    (loop for i from 1 below n
          do (if (= (aref vs i) (aref vs (- i 1)))
                 (setf (aref prevs i) (+ (aref prevs (- i 1)) 1))
                 1))
    (let ((chunks (copy-seq prevs))
          (i (- n 1)))
      (declare ((simple-array uint32 (*)) chunks))
      (loop (when (<= i 0)
              (return))
            (loop for j from i downto 0
                  until (= 1 (aref chunks j))
                  do (setf (aref chunks j) (aref chunks i))
                  finally (setf (aref chunks j) (aref chunks i))
                          (setf i (- j 1))))
      (println
       (loop for end from a to b
             for score = (/ (loop for i below end sum (aref vs i) of-type uint62) end)
             when (= score max-score)
             sum (binomial-coefficient (aref chunks (- end 1)) (aref prevs (- end 1)))
             of-type uint62)))))

#-swank(main)



Measured memory_bytes: 33248