提示: 欢迎访问OurACM平台。
Problem 1702 query

Accept: 90    Submit: 223
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

After Cxw’s Priestess of the Moon defeated by CCQ’s Storm Spirit. Cxw decides not to play Dota again.He spends more time on Algorithm and Data Structure.But one day he meets one puzzle. It shows that :We can get the median number of a sequence easily if the sequence is sorted.But now we dynamically input numbers into the sequence one by one,and ask you to find the median number dynamically.(if the current numbers are odd then return the median number ,but if the current numbers are even then return the less one of the two median numbers)
After Cxw’s Priestess of the Moon defeated by CCQ’s Storm Spirit. Cxw decides not to play Dota again.He spends more time on Algorithm and Data Structure.But one day he meets one puzzle. It shows that :We can get the median number of a sequence easily if the sequence is sorted.But now we dynamically input numbers into the sequence one by one,and ask you to find the median number dynamically.(if the current numbers are odd then return the median number ,but if the current numbers are even then return the less one of the two median numbers)
For example:
If the total number of the sequence is 5.
first: Input 1 return 1
then : Input 2 return 1
then : Input 4 return 2
then : Input 5 return 2
finally:Input 3 return 3
So the input sequence is: 1 2 4 5 3
Then the answer is 1 1 2 2 3
Can anyone help him to solve the problem?

Input

The first line of input is an integer T representing the number of test cases to follow. Each case consists of two lines of input: the first line contain one integer n (0< n< 30000),the second line contain n numbers A0,A1,…A(n-1) representing the input sequence. (The element value of the array will fit in a signed 32-bit integer.)

Output

For each test output the answer sequence. Please separate the n numbers by a space.

Sample Input

2 5 1 2 4 5 3 5 2 1 2 3 5

Sample Output

1 1 2 2 3 2 1 2 2 2

Source

FOJ-2009年4月月赛 cxw

Submit  Back  Status  Discuss