Fast Fourier Transform

You are given a sequence of real numbers of length \(n\) (where \(n\) is a power of two) and you are required to compute its Fast Fourier Transform (FFT) using the Cooley-Tukey algorithm. The FFT is defined as:

\(X_k = \sum_{j=0}^{n-1} x_j \cdot e^{-2\pi i \cdot j \cdot k / n}\), for \(k = 0, 1, \ldots, n-1\).

The output should be a single line containing \(n\) complex numbers separated by spaces. Each complex number must be formatted as real+imagj with exactly five decimal places (for example, 1.00000+0.00000j).

inputFormat

The first line of input contains an integer \(n\) (where \(n\) is a power of two).

The second line contains \(n\) real numbers separated by spaces representing the input sequence.

outputFormat

Output a single line containing \(n\) complex numbers separated by spaces. Each complex number must be printed in the format real+imagj with each part rounded to exactly five decimal places.

2
0 1

1.00000+0.00000j -1.00000+0.00000j