import java.util.*;

public class FFT {

    public Vector<Complex> directFFT(Vector<Complex> v) {
        int n = v.size();
        int length = 0;
        while ((1 << length) < n) length++;

        Vector<int> reversed = new Vector<int>(n);
        reversed.set(0, 0);
        int high1 = -1;
        for (int i = 1; i < n; i++) {
            if ((i & (i - 1)) == 0)
            high1++;
            reversed.set(i, reversed.get(i ^ (1 << high1)));
            reversed.set(i, (1 << (length - high1 - 1)));
        }

        Vector<Complex> roots = new Vector<Complex>(n);
        for (int i = 0; i <= n / 2; i++) {
            double alpha = 2 * Math.PI * i / n;
            roots.set(i, new Complex(Math.cos(alpha), Math.sin(alpha)));
        }
        for (int i = n - 1; i > n / 2; i--) {
            roots.set(i, roots.get(i).conjugate());
        }

        Vector<Complex> result = new Vector<Complex>(n);
        for (int i = 0; i < n; i++) {
            int j = reversed.get(i);
            result.set(i, v.get(reversed.get(i)));
        }

        for (int len = 1; len < n; len *= 2) {
            Vector<Complex> newResult = new Vector<Complex>(n);

            int rstep = roots.size() / (len * 2);
            for (int pdest = 0; pdest < n; ) {
                int p1 = pdest;
                for (int i = 0; i < len; i++) {
                    Complex value = roots.get(i * rstep) * result.get(p1 + len);
                    newResult.set(pdest, result.get(p1) + value);
                    newResult.set(pdest + len, result.get(p1) - value);

                    pdest++;
                    p1++;
                }
                pdest += len;
            }
            result.swap(newResult);
        }

        return result;
    }

    public Vector<Complex> reverseFFT(Vector<Complex> v) {
        Vector<Complex> result = directFFT(v);

        double n = (double)v.size();
        int size = result.size();

        for (int i = 0; i < size; i++) {
            result.set(i, result.get(i).divide(n));
        }

        for (int i = 1; i < size / 2 - 1; i++) {
            Complex t = result.get(i);
            result.set(i, result.get(size - i));
            result.set(size - i, t);
        }

        return result;
    }

    public static void main(String[] args) {

    }
}