Product of Array Except Self

You are given a list of n integers. Your task is to compute a new list where the value at each index i is equal to the product of all the numbers in the original list except the one at index i.

More formally, if the original list is \(a = [a_0, a_1, \dots, a_{n-1}]\), then you need to compute the list \(b\) such that:

\(b_i = \prod_{\substack{0 \le j < n \\ j \neq i}} a_j\)

Your solution should run in O(n) time and should not use division.

inputFormat

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

outputFormat

Output via standard output (stdout) a single line containing n space-separated integers: the product of all numbers except self for each index in the order of input.

4
1 2 3 4

24 12 8 6