Product Except Self

Given an integer array \(A = [a_0, a_1, \dots, a_{n-1}]\), compute a new array \(B\) such that each element \(B[i]\) is equal to the product of all elements of \(A\) except \(a_i\). In other words, \(B[i] = \prod_{\substack{0 \le j < n \\ j \neq i}} a_j\). You must solve this problem without using division.

The array \(A\) may contain positive numbers, negative numbers, and zeros. Your solution should run in O(n) time while using O(1) extra space (ignoring the space used for the output array).

Example:

Input: 4
       1 2 3 4
Output: 24 12 8 6

inputFormat

The first line of input contains a single integer \(n\), representing the number of elements in the array.

The second line contains \(n\) space-separated integers, which are the elements of the array \(A\).

You can assume \(1 \le n \le 10^5\) and \(-10^9 \le a_i \le 10^9\).

outputFormat

Output a single line containing \(n\) space-separated integers. The \(i^{th}\) integer should be equal to \(B[i] = \prod_{\substack{0 \le j < n \\ j \neq i}} a_j\), the product of all array elements except the \(i^{th}\) one.

## sample

4
1 2 3 4

24 12 8 6

</p>