Zadanie

Coronové štatistiky

Počet bodov: 20

Dávid si všimol, že v poslednom čase sa všetci oháňajú nejakým sedemdňovým kĺzavým mediánom. Je presvedčený o tom, že to nie je iba obyčajný medián. Krtko mu pochopiteľne neverí a tvrdí, že je to obyčajný medián hodnôt za posledných $7$ dní. Keďže ani jeden nevie presvedčiť toho druhého o svojej pravde, rozhodli sa, že každý si to naprogramuje a potom porovnajú výsledky s dostupnými dátami.

Pridajte sa ku nim a porovnajte aj svoju implementáciu sedemdňového kĺzavého mediánu.

Vstup a výstup

Na prvom riadku vstupu sa nachádza číslo $n$ – počet dní. Platí $7 \leq n \leq 10^5$.

Na druhom riadku vstupu je $n$ nie nutne rôznych čísiel $c_1,\,\dots,\,c_n$ z rozsahu od $1$ po $10^7$ – počty nakazených v jednotlivých dňoch.

Na jediný riadok výstupu vypíšte medzerou oddelené sedemdňové kĺzavé mediány, od $7.$ po $n$-tý deň.

Dajte si pozor, aby ste za posledným číslom nevypisovali medzeru.

Príklad

Input:

10
5 8 3 5 7 6 3 2 9 9

Output:

5 5 5 6