A stream of financial transactions arrives one at a time.

After each transaction is received, determine the median of all transaction values seen so far.

The median is defined as:

• If the number of values is odd, the median is the middle value after sorting.
• If the number of values is even, the median is the average of the two middle values.

Return the median after every insertion.

To avoid floating-point precision issues, if the median is not an integer, return it as a value ending in .5 (or according to the platform's required format).

---

Input Format

• The first line contains an integer N, the number of transactions.
• The second line contains N space-separated integers representing the transaction values.

---

Output Format

Print N lines, where the i-th line contains the median after processing the first i transactions.

---

Constraints

• 1 ≤ N ≤ 2 × 10^5
• -10^9 ≤ transaction[i] ≤ 10^9

---

Sample Input

5
5 15 1 3 8

Sample Output

5
10
5
4
5

---

Explanation

The medians after each insertion are:

Transactions Seen	Sorted Order	Median
5	5	5
5, 15	5, 15	10
5, 15, 1	1, 5, 15	5
5, 15, 1, 3	1, 3, 5, 15	4
5, 15, 1, 3, 8	1, 3, 5, 8, 15	5