Product Except Self

Given an array of N integers, your task is to compute an output array such that each element at index i is equal to the product of all the elements of the input array except the element at index i.

You must solve the problem in O(N) time and are not permitted to use the division operation. Instead, consider performing two passes through the array: one from the left and one from the right.

The final output should be printed to stdout as a single line of space-separated integers.

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 representing the elements of the array.

outputFormat

Output a single line containing N space-separated integers, where the iᵗʰ integer is the product of all the numbers in the input array except the number at index i.## sample

5
1 2 3 4 5

120 60 40 30 24