#include
#include
#include
using namespace std;
void downheapify(vector &heap,int idx){
int leftidx=2idx+1;
int rightidx=2idx+2;
if(leftidx>=heap.size() && rightidx>=heap.size()){
return;
}
int largestidx=idx;
if(leftidx<heap.size() && heap[leftidx]>heap[largestidx]){
largestidx=leftidx;
}
if(rightidx<heap.size() && heap[rightidx]>heap[largestidx]){
largestidx=rightidx;
}
if(largestidx==idx){
return;
}
swap(heap[idx],heap[largestidx]);
downheapify(heap,largestidx);
}
void upheapifymax(vector &heap1,int idx){
if(idx==0){
return;
}
int parentidx=(idx-1)/2;
if(heap1[parentidx]<heap1[idx]){
int temp=heap1[parentidx];
heap1[parentidx]=heap1[idx];
heap1[idx]=temp;
upheapifymax(heap1,parentidx);
}
else{
return;
}
}
void upheapifymin(vector &heap2,int idx){
if(idx==0){
return;
}
int parentidx=(idx-1)/2;
if(heap2[parentidx]>heap2[idx]){
int temp=heap2[parentidx];
heap2[parentidx]=heap2[idx];
heap2[idx]=temp;
upheapifymin(heap2,parentidx);
}
else{
return;
}
}
void deletepeek(vector &heap){
swap(heap[0],heap[heap.size()-1]);
heap.pop_back();
downheapify(heap,0);
}
void insertmax(vector &heap1,int key){
heap1.push_back(key);
upheapifymax(heap1,heap1.size()-1);
}
void insertmin(vector &heap2,int key){
heap2.push_back(key);
upheapifymin(heap2,heap2.size()-1);
}
vector medianinastream(vector m){
vector result;
vector heap1;
vector heap2;
int avg=INT_MAX;
for(int i=0;i<m.size();i++){
if(m[i]>avg){
insertmin(heap2,m[i]);
}
else{
insertmax(heap1,m[i]);
}
if((heap1.size()-heap2.size())>1 || (heap1.size()-heap2.size())<-1){
if(heap1.size()>heap2.size()){
while((heap1.size()-heap2.size())>1){
int no=heap1[0];
insertmin(heap2,no);
deletepeek(heap1);
}
}
else{
while((heap2.size()-heap1.size())>1){
int no=heap2[0];
insertmin(heap1,no);
deletepeek(heap2);
}
}
}
if((heap1.size()-heap2.size())==0){
avg=(heap1[0] + heap2[0])/2;
}
if((heap1.size()-heap2.size())==1 || (heap1.size()-heap2.size())==-1){
if(heap1.size()>heap2.size()){
avg=heap1[0];
}
else{
avg=heap2[0];
}
}
result.push_back(avg);
}
return result;
}
int main() {
int t;
cin>>t;
while(t>0){
int n;
cin>>n;
vector m;
for(int i=0;i<n;i++){
int x;
cin>>x;
m.push_back(x);
}
vector<int> median=medianinastream(m);
for(auto x:median){
cout<<x<<" ";
}
cout<<endl;
t--;
}
return 0;
}