Product Except Self

You are given an array of n integers. Your task is to compute a new array where each element at index i is equal to the product of all the numbers in the original array except the one at index i. The catch is that you must solve this problem in O(n) time without using division.

Formula: For an input array A, the output array B should be defined as:

[ B[i] = \prod_{j \neq i} A[j] ]

Example:

Input:  [1, 2, 3, 4]
Output: [24, 12, 8, 6]

inputFormat

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

outputFormat

Output a single line containing the resulting array of n elements separated by spaces. Each element is the product of all input numbers except the number at that position.

4
1 2 3 4

24 12 8 6