7267번 - Plaukimo varžybos 서브태스크다국어

Lietuvos atvirosiose mokinių plaukimo varžybose gali dalyvauti visi norintys mokiniai. Kadangi išankstinė registracija nėra būtina, organizatoriai niekada nežino, kiek gali sulaukti norinčiųjų varžytis.

Nors baseine yra 8 plaukimo takeliai, šį kartą mokinių atvyko mažiau nei buvo tikėtasi, todėl organizatoriai nusprendė juos paskirstyti į mažesnes grupes po ne mažiau nei A ir ne daugiau nei B vienoje.

Taip pat organizatoriai siekia, kad kiekvienas plaukimas būtų kuo įdomesnis ir jame dalyvautų kuo panašesnio pajėgumo sportininkai.

Parašykite programą, kuri suskirstytų atvykusius mokinius į plaukimus taip, kad absoliutus skirtumas tarp bent kuriame plaukime dalyvaujančių lėčiausio ir greičiausio plaukikų vidutinių distancijos įveikimo laikų būtų kuo mažesnis.

Pirmojoje eilutėje pateikti trys skaičiai atskirti tarpu: į varžybas atvykusių dalyvių skaičius (N) bei minimalus (A) ir maksimalus (B) viename plaukime galinčių dalyvauti plaukikų skaičius.

Tolimesnėse N eilučių didėjimo tvarka pateikti laikai t_i, per kurį vidutiniškai kiekvienas plaukikas įveikia distanciją (t_i ≤ t_i+1).

Pradiniai duomenys visada bus tokie, kad sprendinys egzistuos.

Jums reikia išvesti vieną skaičių – didžiausią laiko skirtumą tarp vieno plaukimo lėčiausio ir greičiausio dalyvių.

• 2 ≤ N ≤ 500 000
• 2 ≤ A ≤ B ≤ 8
• 1 ≤ t_i ≤ 1 000 000