Problem 1464 --Medium1464: Medium
Time Limit: 3 Sec Memory Limit: 128 MB
Submit: 744 Solved: 258
[Submit][Status][Web Board]Description
Given an array of length \(N\): \(A_1,A_2,...A_N\). For every \(1\leq i\leq N\), you are asked to figure out the medium of \(A_1,A_2,...A_i\). The medium of \(A_1,A_2,...A_i\) is defined as the \({\lceil i/2\rceil}^{th}\) element of \(\{A_i\}\) after it is sorted.
Input
The first line contains one integer \(N(1\leq N\leq 5\times 10^5)\)
The second line contains \(N\) integers \(A_1,A_2,...A_N(1\leq A_i\leq 10^9)\)
Output
Output \(N\) integers in a single line separated by spaces, the \(i^{th}\) of which represents the medium of \(A_1,A_2,...A_i\)
Sample Input
5
2 5 1 4 7
Sample Output
2 2 2 2 4
HINT
Source
[Submit][Status]