Product Except Self

Given an array of integers, your task is to output a new array where each element at index i is equal to the product of all the elements in the original array except the one at index i. Formally, for an input array \( a = [a_0, a_1, \dots, a_{n-1}] \), you need to compute an output array \( output \) such that

\( output_i = \prod_{\substack{0 \leq j < n \\ j \neq i}} a_j \)

This must be done in O(n) time without using division. The solution should handle edge cases including zeros and negative numbers.

inputFormat

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

outputFormat

Output a single line containing n space-separated integers. The i-th integer should be the product of all the array elements except the element at index i.

5
1 2 3 4 5

120 60 40 30 24