CRISIS ALERT! AUCPL inc. has been targeted by a DDoS attack from a rogue employee, Kevin. The entire mainframe is down, but Manager Tom "The Lambda" Frew desperately needs the ongoing seed metrics for his big round bird belly.

But there is a solution! Dump all of the work to Rory the Intern!

Rory the Intern has been handed a stack of ~N~ price records but Tom "The Lambda" Frew is getting antsy, and constantly wants the median seed prices.

Since rogue employee Kevin has somehow deleted Excel off everyone's computer (possibly out of spite), Rory the Intern needs to program to compute the running median quickly.

The price numbers arrive in a specific order. You need to output the median of the numbers Rory the Intern has entered so far, immediately after each number is added.

Recall that for the definition of a median: If there are ~L~ numbers in the spreadsheet, through sorting them in non-decreasing order,

• If ~L~ is odd, the median is the exact middle number
• If ~L~ is even, there are two middle elements. Since Tom "The Lambda" Frew is optimistic, Rory the Intern must report the smaller of the two middle elements.

Formally, the median is the element located at index ~\lfloor\frac{L}{2}\rfloor~ in the 0-indexed sorted list.

Input

The first line contains a single integer ~N~ (~1 \le N \le 2 \times 10^5~), the total number of seed prices Rory the Intern has to enter.

The second line contains ~N~ space-separated integers ~a_1, a_2, \dots, a_N~ (~1 \le a_i \le 10^9~), representing the seed prices in the exact order Rory the Intern types them into the spreadsheet.

Output

Print ~N~ space-separated integers. The ~i~-th integer should be the median of the first ~i~ seed prices.

Example

Input 1

5
10 20 5 15 30

Output 1

10 10 10 10 15

• The list is [10]. The median is 10.
• The list is [10, 20]. Even length, the two middle elements are 10 and 20. The smaller is 10.
• The sorted list is [5, 10, 20]. The middle element is 10.
• The sorted list is [5, 10, 15, 20]. Even length, the middle elements are 10 and 15. The smaller is 10.
• The sorted list is [5, 10, 15, 20, 30]. The middle element is 15.

Input 2

3
67 68 69

Output 2

67 67 68