Product Except Self

Given a list of integers, compute a new list where the value at each index i is the product of all the numbers in the original list except the one at index i. In other words, for each valid index i, compute

$$answer[i] = \prod_{\substack{j=0 \\ j \ne i}}^{n-1} nums[j]$$

The list may contain positive, negative integers and zeros. You need to implement the solution in such a way that it runs in O(n) time and uses O(1) extra space (excluding the output array).

inputFormat

The input is read from standard input (stdin). The first line contains an integer n representing the number of elements in the list. The second line contains n space-separated integers.

outputFormat

Print a single line to standard output (stdout) containing n space-separated integers. The i-th integer should be the product of all elements of the input list except the one at index i.## sample

5
1 2 3 4 5

120 60 40 30 24