Product Array Except Self

Given an array of integers, your task is to compute an output array where each element at index i is equal to the product of all the numbers in the original array except the one at i. You must solve this problem in O(n) time complexity and without using division.

For example, if the input array is [1, 2, 3, 4], the output array should be [24, 12, 8, 6] because:

• For index 0: 2 × 3 × 4 = 24
• For index 1: 1 × 3 × 4 = 12
• For index 2: 1 × 2 × 4 = 8
• For index 3: 1 × 2 × 3 = 6

The mathematical formulation is given by:

\( output[i] = \prod_{\substack{0 \leq j < n \\ j \neq i}} nums[j] \)

inputFormat

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

For example:

4
1 2 3 4

outputFormat

Output a single line with n space-separated integers, where the i-th integer is the product of all the elements of the array except the one at index i.

For the above example, the output should be:

24 12 8 6

## sample

4
1 2 3 4

24 12 8 6