Aikaraja: 5 s

Uolevi on sijoittanut rahaa erään firman osakkeisiin ja seuraa kurssin kehitystä päivittäin. Maija epäilee kuitenkin, onko touhussa järkeä.

Eräänä päivänä Uolevi päätti todistaa Maijalle, että sijoitus on ollut kannattava, kunhan tarkastellaan sopivaa ajanjaksoa. Sitä varten Uolevi tarvitsee kuitenkin apuasi.

Kun annettuna on osakkeen hinta n päivän aikana, tehtäväsi on etsiä joka päivälle sellainen kyseiseen päivään päättyvä ajanjakso, että hinnan keskiarvo on siinä mahdollisimman suuri.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: päivien määrä.

Tämän jälkeen syötteessä on n kokonaislukua a_1,a_2,\ldots,a_n: osakkeen arvo kunakin päivänä.

Tuloste

Ohjelmasi tulee tulostaa n kokonaislukua: kuhunkin päivään päättyvän ajanjakson pituus, jossa osakkeen hinnan keskiarvo on korkein.

Jos mahdollisuuksia on monia, tulosta mahdollisimman pitkä ajanjakso.

Esimerkki

Syöte:

7
1 6 4 6 2 5 5

Tuloste:

1 1 2 1 4 1 2

Selitys: Tarkastellaan esimerkiksi päivää, jolloin osakkeen arvo oli 2. Tähän päivään päättyvät keskiarvot ovat \frac{1+6+4+6+2}{5}=3.8, \frac{6+4+6+2}{4}=4.5, \frac{4+6+2}{3}=4, \frac{6+2}{2}=4 ja \frac{2}{1}=2. Näistä korkein keskiarvo saadaan valitsemalla ajanjakso 4 päivää.

Osatehtävä 1 (12 pistettä)

• 1 \le n \le 200
• 1 \le a_k \le 10^6

Osatehtävä 2 (17 pistettä)

• 1 \le n \le 5000
• 1 \le a_k \le 10^6

Osatehtävä 3 (71 pistettä)

• 1 \le n \le 10^6
• 1 \le a_k \le 10^6