int maxdepth = 50;
int tw[4][10];
int twsize[4];
size_t dsknum;
int dsk;
int cache[1048576];

int hanoi2()
{
    static int depth = 0;
    if (dsk == 0) return 0;
    if (depth >= maxdepth) return 255;    
    int moves_n_depth = cache[dsk];
    if (moves_n_depth && depth+1 >= (moves_n_depth & 255)) 
        return moves_n_depth >> 8;
    ++depth;
    cache[dsk] = (255 << 8) | depth;
    int moves = 255;        
    for (int ti1 = 0; ti1 < 3; ti1++) {
        for (int ti2 = ti1 + 1; ti2 < 4; ti2++) {
            int di1 = twsize[ti1] ? tw[ti1][twsize[ti1]-1] : 255;
            int di2 = twsize[ti2] ? tw[ti2][twsize[ti2]-1] : 255;
            bool rev = (di1 > di2);
            if (rev) swap(ti1, ti2);
            auto& t1 = tw[ti1];
            auto& t2 = tw[ti2];
            if (!twsize[ti1]) continue;
            int db = (rev ? di2 : di1) << 1;
            dsk &= ~(3 << db);
            dsk |= (ti2 << db);
            t2[twsize[ti2]++] = t1[--twsize[ti1]];
            moves = min(moves, hanoi2() + 1);
            t1[twsize[ti1]++] = t2[--twsize[ti2]];
            dsk &= ~(3 << db);
            dsk |= (ti1 << db);
            if (rev) swap(ti1, ti2);
        }
    }
    cache[dsk] = (moves << 8) | depth;
    --depth;
    return moves;
}

int hanoi(vector<int> posts)
{
    for (maxdepth = 10; maxdepth <= 50; maxdepth += 20) {
        cout << "maxdepth=" << maxdepth << "\n";
        dsknum = posts.size();
        fill(&tw[0][0], &tw[0][0]+sizeof(tw)/sizeof(tw[0][0]), 0);
        fill(twsize, twsize +sizeof(twsize)/sizeof(twsize[0]), 0);
        fill(cache, cache + sizeof(cache)/sizeof(cache[0]), 0);
        dsk = 0;
        for (auto di = 0; di < dsknum; di++) {
            int ti = posts[di] - 1;
            dsk |= (ti << (di << 1));
            tw[ti][twsize[ti]] = di;
            twsize[ti]++;
        }
        for (int ti = 0; ti < 4; ti++)
            sort(tw[ti], tw[ti] + twsize[ti], greater<int>());

        int result = hanoi2();
        if (result < 255)
            return result;
    }
    return 255;
}