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