public class Kaannot {
    public static int[] perm = {7,13,9,4,1,14,5,3,12,10,15,2,8,6,11};
    public static boolean valmis = false;
    public static int[][] historia = new int[50][2];

    public static int arvio() {
        int tulos = 0;
        for (int i = 0; i < perm.length-1; i++) {
            if (Math.abs(perm[i]-perm[i+1]) != 1) tulos++;
        }
        if (perm[0] != 1) tulos++;
        if (perm[perm.length-1] != perm.length) tulos++;
        if (tulos%2 == 1) tulos++;
        return tulos/2;
    }

    public static void kaanna(int alku, int loppu) {
        int pituus = loppu-alku+1;
        for (int i = 0; i < pituus/2; i++) {
            int v = perm[alku+i];
            perm[alku+i] = perm[loppu-i];
            perm[loppu-i] = v;
        }
    }

    public static void tulosta(int kohta) {
        kaanna(historia[kohta][0], historia[kohta][1]);
        if (kohta > 0) tulosta(kohta-1);
        for (int i = 0; i < perm.length; i++) {
            System.out.print(perm[i] + " ");
        }
        System.out.println();
        kaanna(historia[kohta][0], historia[kohta][1]);
    }

    public static void haku(int maara, int raja) {
        if (valmis) return;
        int arvio = arvio();
        if (arvio == 0) {
            System.out.println("Lyhin sarja: " + maara);
            tulosta(maara);
            valmis = true;
            return;
        }
        if (maara+arvio > raja) return;
        for (int i = 0; i < perm.length; i++) {
            for (int j = i+1; j < perm.length; j++) {
                kaanna(i, j);
                historia[maara][0] = i;
                historia[maara][1] = j;
                haku(maara+1, raja);
                kaanna(i, j);
            }
        }
    }

    public static void main(String[] args) {
        for (int i = 0; ; i++) {
            haku(0, i);
            if (valmis) break;
        }
    }
}