Laiko ribojimas: 1s

Atminties ribojimas: 256MB

Duomenų failas: rykliai.in

Rezultatų failas: rykliai.out

Jei norite pateikti savo sprendimą - prisijunkite.

3. Rykliai

Jau daug metų mokslininkai studijuoja ryklius. Rykliai, kaip ir daugelis kitų gyvūnų, keliauja trumpais atstumais tam tikrame regione arba ilgais atstumais tarp regionų.

Armachadelijus yra jaunas biologas. n dienų jis stebėjo vieną konkretų ryklį ir išmatavo atstumą, kurį ryklys nukeliavo kiekvieną dieną. Armachadelijus nori žinoti, kiek regionų ryklys aplankė. Jis padarė prielaidą, jog egzistuoja toks sveikasis skaičius k, jog jei ryklys tam tikrą dieną nukeliavo griežtai mažesnį atstumą, nei k, tai jis nekeitė regiono. Kitu atveju, jei ryklys tam tikrą dieną nukeliavo atstumą, lygų arba didesnį nei k, tai jis tą dieną keitė regioną. Pastaba: yra įmanoma, jog ryklys keitė regioną kelias dienas iš eilės, kiekvieną iš dienų nukeliaudamas bent k atstumą ir kitą regioną pasiekė tik per kelias dienas.

Ryklys niekad negrįžo į jau aplankytą regioną. Reiškiasi, n dienų sekoje galime rasti iš eilės einantį netuščią segmentą dienų, kai ryklys kiekvieną dieną nuplaukdavo atstumą mažesnį nei k: kiekvienas toks segmentas reiškia, jog ryklys buvo tam pačiam regione. Armachadelijus nori parinkti tokį k, kad visų tokių segmentų ilgiai būtų lygūs.

Raskite tokį sveikąjį skaičių k, kad aplankytų regionų skaičius būtų kuo didesnis. Jei egzistuoja keli tokie k, išveskite mažiausią.

Pastaba: segmente esančių skaičių kiekis turi būti didesnis už 0.

Pastaba 2: Ryklys aplanko regioną tik tuomet, jei jame praleidžia bent vieną dieną.

Pradiniai duomenys

Pirmoje eilutėje pateiktas vienas skaičius n (1\\leqn\\leq100000) - dienų skaičius. Sekančioje eilutėje pateikta n skirtingų teigiamų sveikųjų skaičių a_1,a_2,...a_n (1\\leqa_i\\leq10^9) - atstumai, nukeliauti kiekvieną dieną.

Rezultatai

Išveskite vieną tokį skaičių k, kad:

  1. Ryklys kiekvienam regione buvo vienodą skaičių dienų.
  2. Aplankytų regionų skaičius yra maksimalus.
  3. k yra mažiausias sveikasis skaičius tenkinantis pirmą ir antrą sąlygas.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
8
1 2 7 3 4 8 5 6
 
7