Annettuna on taulukko, jossa on n kokonaislukua. Tehtäväsi on etsiä kussakin kohdassa kyseiseen kohtaan päättyvä alitaulukko, jonka keskiarvo on mahdollisimman suuri.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: taulukon koko.

Tämän jälkeen syötteessä on n kokonaislukua a_1,a_2,\ldots,a_n: taulukon sisältö.

Tuloste

Tulosta n kokonaislukua: kussakin kohdassa alitaulukon pituus. Jos mahdollisia alitaulukoita on useita, tulosta niistä pisimmän pituus.

Esimerkki

Syöte:

7
1 6 4 6 2 5 5

Tuloste:

1 1 2 1 4 1 2

Selitys: Tarkastellaan esimerkiksi kohtaa, jossa on luku 2. Tähän kohtaan 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 pituuden 4 alitaulukko.

Osatehtävä 1 (12 pistettä)

• 1 \le n \le 100
• 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^5
• 1 \le a_k \le 10^6