Three rings for the elven kings
In the forge of Mendeleev, the blacksmith Celebrimbor crafts a new ring each year and places it on a shelf. At the end of every year, Gorthaur, an inspector from the Mendeleev Inspection Service, visits to identify the ring with the median mass and records its weight in his notebook. If the number of rings is even, Gorthaur selects the lighter of the two middle rings.
Given the mass of each ring forged by Celebrimbor over N years, determine the entries in Gorthaur's notebook after these N years.
Input
The first line contains the integer N (1 ≤ N ≤ 1000). The second line provides N natural numbers, each not exceeding 10000, representing the weights of the rings in the order they were created.
Output
Output N numbers separated by spaces, representing the masses of the rings selected by Gorthaur in the order they were chosen.