Най-накрая дойде момента за нанасяне на оценките по ДАА. Ели и колегите ѝ стоят в очакване да дойде и техния ред за това. Като при повечето изпити, след излизането на всеки от студентите, той веднага бива наобиколен от няколко свои колеги да бъде обстойно разпитан какво са го питали и колко са му писали. По досегашните оценки студентите, които все още не са минали, могат да определят каква е средната оценка.

Елеонора е забелязала, че медианата на досегашните оценки е далеч по-добра метрика колко "гаден" е даден изпит, отколкото средно аритметично. Медиана на N числа е числото, което получаваме като сортираме N-те числа и:

• Вземем това по средата, ако N е нечетно
• Вземем средното аритметично на двете числа по средата, ако N е четно

Ели няма никакъв проблем да намира медианата наум, независимо колко много студенти има на изпита. Вие, за съжаление, нямате нейните възможности и затова решавате да си напишете програма, която прави това. По даден брой N на студентите, които минават преди вас, вие искате да намерите медианата на досега миналите след излизането на всеки от тях (тоест първо медианата на първия, после медианата на първия и втория, после медианата на първия, втория и третия и т.н.). Стандартният вход съдържа два реда, като на първия от тях е зададен броят на студентите N. На втория ред ще има N цели числа A₁, A₂, …, A_N, разделени с по един интервал – оценките на всеки от студентите. Университетът, в който учи тя (СУортс), е малко странен и оценките са между 1 и 1,000,000,000, включително. На единствен ред на стандартния изход изведете N числа, разделени с по един интервал – i-тото от които е медианата на първите i числа. Изведете числата с точно една цифра след десетичната точка.

• 1 ≤ N ≤ 200,000
• 1 ≤ A_i ≤ 1,000,000,000

Примерен Вход	Примерен Изход
5 42 13 11 17 666	42.0 27.5 13.0 15.0 17.0
7 1 2 3 4 5 6 7	1.0 1.5 2.0 2.5 3.0 3.5 4.0