Insert Zeroes Between Same-Signed Numbers

You are given a sequence of integers. Your task is to process this sequence and insert a zero between two adjacent numbers if they have the same sign, that is, if both are positive or both are negative. Formally, for every adjacent pair of numbers (a_{i-1}) and (a_{i}), if (a_{i-1} \times a_{i} > 0), then insert a zero between them. If the input sequence is empty, simply output an empty sequence. The final output should be the modified sequence printed as space-separated integers.

inputFormat

The input is given via standard input (stdin). The first line contains an integer (n) denoting the number of elements in the sequence. The second line contains (n) space-separated integers representing the elements of the sequence.

outputFormat

Output the modified list as a sequence of space-separated integers on one line using standard output (stdout).## sample

1
1

1