Product of Array Except Self

Given an array of integers \(A = [a_1, a_2, \ldots, a_n]\), compute an output array \(B\) where each element \(b_i\) is given by \(b_i = \prod_{\substack{j=1 \\ j\neq i}}^{n} a_j\). In other words, for every index \(i\), multiply all the numbers in the array except \(a_i\). You are not allowed to use the division operation when solving this problem.

For example, if \(A = [1, 2, 3, 4]\), then the output \(B\) should be \( [24, 12, 8, 6]\) because:

[ \begin{aligned} 24 &= 2 \times 3 \times 4,\ 12 &= 1 \times 3 \times 4,\ 8 &= 1 \times 2 \times 4,\ 6 &= 1 \times 2 \times 3. \end{aligned} ]

If the array has a single element, the output should be [1].

Take note that the array may contain zeros or negative numbers. Your solution should work in \(O(n)\) time and use constant extra space besides the output array.

inputFormat

The input is read from standard input (stdin). The first line contains an integer (n) ((1 \le n \le 10^5)), the number of elements in the array. The second line contains (n) space-separated integers representing the array (A).

outputFormat

Output to standard output (stdout) a single line containing (n) space-separated integers, where the (i)-th integer is the product of all elements of (A) except (a_i).## sample

4
1 2 3 4

24 12 8 6