对于一个递增序列，序列中每个元素从 1 开始编号，假设该序列有 n 个元素。

该数列的中心数，是编号为 \lceil n/2 \rceil 的元素的值。如果数列本身无序，需要先排序才能计算中心数。

\lceil x \rceil 表示对 x 向上取整。

例如，一个递增序列为 {1, 4, 7, 10} ，编号依次为 {1, 2, 3, 4} ，该序列有 4 个元素，因此该数列的中心数是编号为 \lceil 4/2 \rceil = 2 的元素，即数字 4。

输入一个数 n (1 \leq n \leq 10^4) ，表示数的总个数。

接着依次输入 n 个数 a_i (1 \leq a_i \leq 10^9) ，每输入一个新的数 a_i 后，都计算并输出一次此时这个数列的中心数。

• 第一行输入一个数字 n (1 \leq n \leq 10^4) ，表示某个序列数的数量。
• 第二行依次输入 n 个数 a_i (1 \leq a_i \leq 10^9) ，中间用空格隔开。

• 输出 n 个整数，每个整数表示一个数字序列的中心数，数字之间用空格隔开。

数据范围与提示

• 输入 7 后，数列为 {7}，排序后为 {7}，中心数输出 7
• 输入 1 后，数列为 {7,1}，排序后为 {1,7}，中心数输出 1
• 输入 10 后，数列为 {7,1,10}，排序后为 {1,7,10}，中心数输出 7
• 输入 4 后，数列为 {7,1,10,4}，排序后为 {1,4,7,10}，中心数输出 4