Product Except Self

Given a list of positive integers, your task is to compute a new list result of the same length such that for every index i, the value result[i] is equal to the product of all the numbers in the input list except the one at index i. Formally, for an array \(a = [a_0, a_1, \dots, a_{n-1}]\), you need to compute:

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

This must be done without using division and in O(n) time complexity. Beware of the edge case when the list contains only one element: in that case, output 1.

The input size can be large (up to \(10^5\) elements), so efficient use of time and space is critical.

inputFormat

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

The second line contains n space-separated positive integers. Each integer is guaranteed to be between 1 and 10⁹.

outputFormat

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

4
1 2 3 4

24 12 8 6