小H前段时间在面试，面试官问了一个中位数的问题：一个长度为n的序列A, 怎么求A所有前缀子串的中位数。小H当时想破头也没想到，所以今天不得不向你求助。可是前缀子串有时候太多了，因此，小H好心帮你减轻工作量，你只用求长度为奇数的前缀子串的中位数。

第一行为n，表示序列长度；随后的n个自然数。

(1e3<=n<=1e5, 1<=a[i]<=1e9)

输出（n + 1）/2个数，分别是子串[0,0],[0,2],[0,4].....的中位数。