import java.util.LinkedList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        int n=12;
        long totalStart = System.nanoTime();
        
        final List<int[]>[] cache = new List[n];

        for (int chordes = 1; chordes <= n; chordes++) {
            long start = System.nanoTime();
            final int points = chordes * 2;

            final List<int[]> partialResult = new LinkedList<int[]>();
            for (int pos = 1; pos < points; pos+=2) {
                int leftDist = pos-1;
                int rightDist = points-pos-1;

                if (leftDist > 0) {
                    List<int[]> left = cache[(leftDist / 2 - 1)];
                    for (int[] lpart : left) {
                        if (rightDist > 0) {
                            List<int[]> right = cache[(rightDist / 2 - 1)];

                            for (int[] rpart: right) {
                                partialResult.add(build(points, pos, lpart, rpart));
                            }
                        } else {
                            partialResult.add(build(points, pos, lpart, null));
                        }
                    }
                } else if (rightDist > 0) {
                    List<int[]> right = cache[(rightDist / 2 - 1)];

                    for (int[] rpart: right) {
                        partialResult.add(build(points, pos, null, rpart));
                    }
                } else {
                    partialResult.add(build(points, pos, null, null));
                }
            }
            cache[chordes-1] = partialResult;
            System.out.println(chordes + "\t" + (System.nanoTime() - start) + " ns");
        }

        final List<int[]> result = cache[n-1];
        System.out.println("Total solutions: " + result.size());
        /*for (int[] r : result) {
            for (int p : r) {
                System.out.print(""+p+",");
            }
            System.out.println();
        }  */
        
        System.out.println("Total time: " + (System.nanoTime() - totalStart)/1000000 + " ms");
    }

    private static int[] build(int points, int pos, int[] lpart, int[] rpart) {
        int[] r = new int[points];
        r[0] = pos;
        r[pos] = 0;
        if (lpart != null) {
            int leftDist = pos-1;
            System.arraycopy(lpart, 0, r, 1, leftDist);
        }
        if (rpart != null) {
            int rightDist = points-pos-1;
            System.arraycopy(rpart, 0, r, pos + 1, rightDist);
        }
        return r;
    }

}