CSES - Leirikisa 9.12.2021 - Pörssihai
  • Time limit: 2.00 s
  • Memory limit: 128 MB

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 nn 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 nn: päivien määrä.

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

Tuloste

Ohjelmasi tulee tulostaa nn 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 22. Tähän päivään päättyvät keskiarvot ovat 1+6+4+6+25=3.8\frac{1+6+4+6+2}{5}=3.8, 6+4+6+24=4.5\frac{6+4+6+2}{4}=4.5, 4+6+23=4\frac{4+6+2}{3}=4, 6+22=4\frac{6+2}{2}=4 ja 21=2\frac{2}{1}=2. Näistä korkein keskiarvo saadaan valitsemalla ajanjakso 44 päivää.

Osatehtävä 1 (12 pistettä)

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

Osatehtävä 2 (17 pistettä)

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

Osatehtävä 3 (71 pistettä)

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