Product Except Self

You are given an array of n integers. Your task is to return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i.

In other words, for an input array a of length n, you need to construct an output array res such that:

\( res[i] = \prod_{\substack{0 \le j < n \\ j \ne i}} a[j] \)

The solution should run in \(O(n)\) time and must handle cases where the array contains zeros and negative numbers.

inputFormat

The first line of input contains a single integer n (1 ≤ n ≤ 10⁵), denoting the number of elements in the array.

The second line contains n space-separated integers representing the elements of the array.

outputFormat

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

4
1 2 3 4

24 12 8 6