+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در اواسط حکومت خشایار شاه بر اسپادانا، یکی از قبایل همسایه- که از بردن نامش چشم‌پوشی می‌کنیم- تصمیم به حمله به اسپادانا گرفت. اما از آن‌جایی که خشایارشاه پادشاهی با کفایت بود، با کمک کیوان خیلی سریع اقدام به تشکیل سپاهی پر قدرت کرد. در اسپادانا، $n$ سرباز با شماره‌های $1$ تا $n$ به ترتیب در یک صف قرار دارند که هوشمندی سرباز $1 \le i \le n$ برابر $a_i$ است. **هوشمندی** یک گروه از سربازها نیز برابر **میانگین هوشمندی** سربازهای آن گروه است. برای مثال هوشمندی یک گروه $3$ نفره از سرباز‌ها با هوشمندی ${1, 3, 4}$ برابر $\frac{8}{3}$ است. از آنجایی که قبیله همسایه در $k$ گروه به اسپادانا حمله می‌کرد، خشایارشاه به کیوان دستور داده بود که سربازها را به حداقل $k$ گروه **افراز** کند. همچنین خشایارشاه دستور داده بود هر گروه از سربازها یک **زیردنباله متوالی** از سربازهای درون صف باشد. به بیان دقیق‌تر کیوان باید سربازها را به حداقل $k$ زیردنباله متوالی افراز کند. **اعتبار** یک گروه بندی توسط کیوان را *مینیمم هوشمندی* بین گروه‌ها تعریف می‌کنیم. برای مثال فرض کنید دنباله $a = <1, 2, 3, 5>$ باشد، و کیوان دنباله را به $2$ زیردنباله متوالی مثل ${1, 2}$ و ${3, 5}$ افراز کند در این‌صورت هوشمندی گروه‌ها برابر $\frac{3}{2}$ و $4$ می‌شود. درنتیجه اعتبار این گروه‌بندی $\frac{3}{2}$ است. از آنجایی که اسپادانا در آن زمان بسیار مقتدر بود، خشایارشاه به کیوان دستور داده بود که اعتبار گروه‌بندی‌اش در بین تمام گروه‌بندی‌های ممکن بیشینه باشد. شما می‌دانید که در آن زمان کیوان حال و روز درست و حسابی نداشته است، به او کمک کنید و بیشینه اعتبار ممکن در بین همه گروه‌بندی‌ها را بیابید. # ورودی در خط اول ورودی دو عدد $n, k$ آماده است. سپس $n$ عدد $a_1, a_2, ..., a_{n}$ آمده است که میزان هوشمندی سرباز‌ها را معین می‌کند. $$1 \le k \le n \le 100\ 000$$ $$0 \le a_i \le 10^{9}$$ # خروجی در تنها خط خروجی, جواب مساله را چاپ کنید. با توجه به اینکه جواب ممکن است اعشاری باشد، جواب شما در صورتی پذیرفته می‌شود که اختلاف آن با جواب بهینه کمتر از $10^{-6}$باشد. # زیر مسئله‌ها | زیرمسئله | نمره | محدودیت | |:---------------------:|:----------------:|:-------------------:| | ۱ | ۱۰ | $k \le 2$| | ۱ | ۲۰ | $n \le 1\ 000$| | ۲ | ۳۰ | $k \le 10$| | ۳ | ۴۰ | بدون محدودیت اضافی| # مثال ## ورودی نمونه ۱ ``` 4 2 2 1 4 3 ``` ## خروجی نمونه ۱ ``` 2.33333333333 ``` ## ورودی نمونه ۲ ``` 4 3 2 1 4 3 ``` ## خروجی نمونه ۲ ``` 2.0000000000 ``` ## ورودی نمونه ۳ ``` 10 4 13 4 7 3 1 17 5 8 7 6 ``` ## خروجی نمونه ۳ ``` 6.499999999 ```