Королівство Гобітів
Обмеження: 2 сек., 256 МіБ
Колись Нострадамус написав: «... настане день, коли на території найбільшої країни світу почнуть масово з’являтися з-під землі Гобіти і заселять вони всю територію тої країни, а місцеве населення з переляку масово піде в запій та й вимре, і не стане великої червоної держави, і весь світ зітхне з полегшенням, а натомість утвориться могутнє королівство Гобітів...»
Усі Гобіти дуже люблять свого короля Хобота Четвертого. На честь утворення королівства народ вирішив влаштувати свято, яке за законами Гобітів має тривати не менше ніж aa, але не більше ніж b днів. Свято може розпочатися не обов’язково цього дня, але має закінчитися не пізніше за день c, ураховуючи, що поточний день перший.
По закінченню свята король винагородить увесь народ деякою кількість золотих монет залежно від того, наскільки йому свято сподобається.
Король дуже теплолюбний, і чим вища буде температура під час свята — тим краще. Він виділить народові суму, що рівна мінімальній температурі протягом свята, помноженій на кількість днів свята.
Вам відома температура в королівстві на наступні c днів.
Необхідно визначити мінімальну та максимальну кількість золотих монет, яку виділить король своєму народові залежно від того, коли саме буде проходити свято.
Вхідні дані
Перший рядок містить три цілих числа a, b, c.
Другий рядок містить c цілих чисел ti — температуру в день i.
Вихідні дані
У першому рядку виведіть три цілих числа: мінімально можливу кількість золотих та перший і останній день свята, для якого ця кількість досягається. Якщо таких свят є декілька — виведіть свято з найбільшою кількість днів. Якщо ж і таких є декілька — свято, що найшвидше почнеться.
У другому рядку виведіть відповідь у такому ж форматі для максимально можливої кількості золотих монет.
Обмеження
1≤a≤b≤c≤105,
1≤ti≤105.
Приклади
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| 2 4 7 1 2 3 4 3 2 1 | 2 1 2 9 3 5 |