Product of Array Except Self

Given an array a of n integers, your task is to compute a new array such that for every index i, the following equation holds:

\(output[i] = \prod_{\substack{0 \le j < n \\ j \ne i}} a[j]\)

You are not allowed to use division in your solution. The algorithm should run in O(n) time complexity and handle cases with zeroes and negative numbers correctly.

Note: The input is read from standard input (stdin) and the output must be printed to standard output (stdout) as space-separated integers.

inputFormat

The first line contains an integer n, representing the number of elements in the array. The second line contains n space-separated integers which represent the elements of the array.

outputFormat

Print a single line with n space-separated integers, where the i-th integer is the product of all the elements of the array except the one at index i.

4
1 2 3 4

24 12 8 6