Given an array x of n elements find the medians of its first k elements for each k from 1 to n inclusive. The median of an array is the middle element of that array when it is sorted. If there are an even number of elements in the array, we choose the first of the middle two elements to be the median.

Input

The first line of input contains number n (1 <= n <= 200000) - the number of elements in the array. The next n lines contain the elements xi (1 <= xi <= 1000000).

Output

Output n integers - the medians of the first k elements of the array for each k from 1 to n inclusive.

Example

Input:
5
1
2
3
4
5

Output:
1
1
2
2
3