Product of Array Except Self

Given an array of integers, you are required to compute a new array res such that the element at index i is equal to the product of all the elements in the original array except the one at i. That is, for every index i:

$$res[i] = \prod_{\substack{j=0 \\ j \neq i}}^{n-1} arr[j]$$

You are not allowed to use division and your solution should run in O(n) time complexity.

inputFormat

The input is read from standard input (stdin) and consists of two lines:

1. The first line contains a single integer n ($1 \leq n \leq 10^5$) representing the number of elements in the array.
2. The second line contains n space-separated integers which are the elements of the array.

outputFormat

Print a single line to standard output (stdout) containing n space-separated integers. The i-th integer is the product of all elements of the input array except the element at the i-th index. Formally, the output array res must satisfy:

$$res[i]=\prod_{j\neq i} arr[j]$$

4
1 2 3 4

24 12 8 6