static private long base;
static private int numOfRods;
static private int INF;

static private int[] fillRods(List<Integer> posts) {
    int[] res = new int[numOfRods];

    int n = posts.size();
    for (int i = 0; i < n; i ++) {
        int rod = posts.get(i) - 1;
        int diskVal = (int) Math.pow(2, i);
                    
        res[rod] += diskVal;    
    }        
    
    return res;
}

public static long findState(int[] rods) {
    long res = 0;
    
    for (int i = 0; i < numOfRods; i++) {
        res += (long) rods[i] * (long) Math.pow(base, numOfRods - i - 1);
    }
    
    return res;
}

public static int[] fromStateToRods(long state) {
    int[] res = new int[numOfRods];
    
    for (int i = 0; i < numOfRods; i ++) {
        res[i] = (int) ((state / Math.pow(base, numOfRods - i - 1)) % base);
    }
    
    return res;
}

public static int[] findTopDisks(int[] curRods) {
    int[] res = new int[numOfRods];
    
    for (int i = 0; i < numOfRods; i++) {
        if (curRods[i] == 0) {
            res[i] = INF;
        }
        else {
            res[i] = curRods[i] ^ (curRods[i] & (curRods[i] - 1));
        }
    }
    
    return res;
}
    
public static int hanoi(List<Integer> posts) { 

    int n = posts.size();
    
    numOfRods = 4;
    base = (long) Math.pow(2, n);
    INF = (int) Math.pow(2, n);
    
    int[] rods = fillRods(posts);
    
    long startState = findState(rods);

//win when disks align at rod 1...
//base - 1 == 2 ** n - 1 : sum of all bits when translated to decimal

    long winState = (base - 1) * (long) Math.pow(base, numOfRods - 1);
    
    LinkedList<ArrayList<Long>> queue = new LinkedList<>();
    TreeMap<Long, ArrayList<Integer>> checked = new TreeMap<>();

//queuing simple wrappers that carry 
//state, 
//type (1, 2 as from start, from end),
//respective moves

//instead of set, using map to store above information

    queue.add(new ArrayList<Long>(Arrays.asList(startState, 1L, 0L)));
    checked.put(startState, new ArrayList<Integer>(Arrays.asList(1, 0)));
    
    queue.add(new ArrayList<Long>(Arrays.asList(winState, 2L, 0L)));
    checked.put(winState, new ArrayList<Integer>(Arrays.asList(2, 0)));

    long state;
    long stateType;
    long stateMoves;
    long toAdd;
    long toSubtract;
    long newState;
    int[] curRods = new int[numOfRods];
    int[] topDisks = new int[numOfRods];
    ArrayList<Long> queueObject;
    
    while (!queue.isEmpty()) {
        
        queueObject = queue.pollFirst();
        
        state = queueObject.get(0);
        stateType = queueObject.get(1);
        stateMoves = queueObject.get(2);

        curRods = fromStateToRods(state);
        topDisks = findTopDisks(curRods);
    
        for (int i = 0; i < 4; i ++) {
            for (int j = i + 1; j < 4; j ++) {
                
                if (topDisks[i] == INF && topDisks[j] == INF) {
                    continue;
                }
                
                if (topDisks[j] < topDisks[i]) {
                    toSubtract = (long) topDisks[j] * (long) Math.pow(base, numOfRods - j - 1);
                    toAdd = (long) topDisks[j] * (long) Math.pow(base, numOfRods - i - 1);
                }
                else {
                    toSubtract = (long) topDisks[i] * (long) Math.pow(base, numOfRods - i - 1);
                    toAdd = (long) topDisks[i] * (long) Math.pow(base, numOfRods - j - 1);
                }
                
                newState = state - toSubtract + toAdd;      
                queueObject = new ArrayList<Long>(Arrays
                                    .asList(newState, stateType, stateMoves + 1));   
                
                if (checked.get(newState) == null) {
                    queue.add(queueObject);
                    checked.put(newState, new ArrayList<Integer>(Arrays
                                    .asList((int) stateType, (int) stateMoves + 1)));
                }

//if states overlap, we found the middle point
//then adding 2 move numbers should give us the total moves

                else if (checked.get(newState).get(0) != stateType) {
                    return (int) stateMoves + 1 + checked.get(newState).get(1);
                }
            }
        }
    }
    
    return -1;
}