Product Except Self

Given an array of integers, return an array such that each element at index (i) is the product of all the numbers in the array except the one at (i). Solve this problem in (O(n)) time without using division. This means you need to compute for every index (i): [ \text{answer}[i] = \prod_{\substack{0 \leq j < n \ j \neq i}} a_j ] where (a_j) are the elements of the input array. The input is read from stdin and the output should be printed to stdout.

inputFormat

The first line contains a single integer (n), the number of elements in the array. The second line contains (n) space-separated integers.

outputFormat

Output a single line containing (n) space-separated integers where the (i)-th integer is the product of all the elements in the input array except the element at index (i).## sample

4
1 2 3 4

24 12 8 6