Product Array Puzzle

Given an array of n integers \(a_1, a_2, \dots, a_n\), your task is to construct a new array \(b\) of the same size such that each element \(b_i\) is equal to the product of all the elements of the original array except \(a_i\). In other words, compute

[ \displaystyle b_i = \prod_{\substack{j=1 \ j\neq i}}^{n} a_j, ]

for \(1 \leq i \leq n\). Note that the array may contain zeros and negative numbers. You are not allowed to use division in your solution.

inputFormat

The first line of the input contains an integer \(n\) representing the number of elements in the array. The second line contains \(n\) space-separated integers representing the array elements \(a_1, a_2, \dots, a_n\).

outputFormat

Output a single line with \(n\) space-separated integers where the \(i\)-th integer is the product of all array elements except the \(i\)-th element of the input array.

5
1 2 3 4 5

120 60 40 30 24