Taco: Fix Speeds on Broken Platforms

In this problem, you are given an integer (n) and an array of (n) integers representing the speeds on a series of platforms. Some platforms are broken, indicated by a speed of -1. Your task is to replace the speed of each broken platform with the speed of its available adjacent platform(s).

If a broken platform has two adjacent valid speeds, replace it by the floor of the average of these two values, i.e., (\left\lfloor\frac{a+b}{2}\right\rfloor). If only one adjacent platform is valid, use that speed as the replacement. If no valid adjacent platform exists, leave the speed as -1.

You need to implement a solution that reads the input from stdin and prints the corrected speeds to stdout.

inputFormat

The input consists of two lines:

1. The first line contains an integer (n) (the number of platforms).
2. The second line contains (n) space-separated integers, where each integer represents the speed of a platform (a speed of -1 indicates a broken platform).

outputFormat

Output a single line containing (n) space-separated integers, representing the speeds after replacing the broken platforms according to the rules.## sample

6
3 -1 5 8 -1 -1

3 4 5 8 8 -1