ac

给定一个整数n，代表汉诺塔游戏中从小到大放置n个圆盘，假设开始所有圆盘都在左边的柱子上，那么用最优的办法把所有圆盘都移动到右边的柱子上的过程，就称为最优移动轨迹。给定一个整型数组arr, 其中只含有1、2和3,代表所有圆盘目前的状态，1代表左柱，2代表中柱，3代表右柱，a[i]的值代表第i+1个圆盘的位置（a[i]下标从0开始）。比如，arr=[3,3,2,1], 代表第1个圆盘在右柱上、第2个圆盘在右柱上、第3个圆盘在中柱上、第4个圆盘在左柱上。如果arr代表的状态是最优移动轨迹过程中出现的状态，输出arr这种状态是最优移动轨迹中的第几个状态（由于答案可能较大，请输出对10^9+7取模后的答案）。如果arr代表的状态不是最优移动轨迹过程中出现的状态，则输出-1。

static void println(int n, String d1, String d2){
    String s = String.format("Move %d from %s to %s", n, d1, d2);
    System.out.println(s);
}

/*
left, mid, right
    */
static int rev(int n, String left, String mid, String right){
    if(n <= 0){
        return 0;
    }
    if(n == 1){
        println(n, left, mid);
        println(n, mid, right);
        return 2;
    }
    int step = 0;
    // n - 1 必须全部从 left -> mid -> right
    // 接着最大的 n 从 left -> mid
    // n - 1 必须全部从 right -> mid -> left
    // n 再 从 mid -> right
    // 至此 完成依次操作，问题由 n 变成 n-1
    // 递归即可
    step += rev(n-1, left, mid, right);
    println(n, left, mid);
    step += 1;
    step += rev(n-1, right, mid, left);
    println(n, mid, right);
    step += 1;
    step += rev(n-1, left, mid, right);
    return step;
}

import java.util.Scanner;


public class Main {

    public static Scanner sc = new Scanner(System.in);

    static int M = (int)Math.pow(10, 9) + 7;

    public static void main(String[] args) {
        int n = sc.nextInt();
        // arr[i] 表示 圆盘i+1所在left/mid/right上
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
        }
        System.out.println(step2(arr));
    }

    static int step1(int[] arr){
        if(arr == null || arr.length == 0){
            return -1;
        }
        return process(arr, arr.length -1, 1,2,3);
    }
    static int process(int[] arr, int i, int left, int mid, int right){
        if(i == -1){
            return 0;
        }
        // i既不在left，又不在right
        if(arr[i] != left && arr[i] != right){
            return -1;
        }
        if(arr[i] == left){// i还在左边, 目标是 i-1 从 left到mid
            return process(arr, i-1, left, right, mid);
        }else {
            // i已经右边了，则目标是 i-1 从mid到right
            int rest = process(arr, i-1, mid, left, right);
            if(rest == -1){
                return -1;
            }
            return (1 << i) + rest;
        }
    }

    static int step2(int[] arr){
        if(arr == null || arr.length == 0){
            return -1;
        }
        int[] count = new int[arr.length];
        count[0] = 1;
        for (int i = 1; i < arr.length; i++) {
            count[i] = (count[i - 1] << 1) % M;
        }
        int left = 1;
        int mid = 2;
        int right = 3;
        int i = arr.length - 1;
        int res = 0;
        while (i >= 0){
            // i既不在left，又不在right
            if(arr[i] != left && arr[i] != right){
                return -1;
            }
            if(arr[i] == left){// i还在左边, 目标是 i-1 从 left到mid
                int tmp = mid;
                mid = right;
                right = tmp;
            }else {
                res += count[i];
                // i已经右边了，则目标是 i-1 从mid到right
                int tmp = left;
                left = mid;
                mid = tmp;
            }
            i--;
            res %= M;
        }
        return res % M;
    }

}
/*
2
1 1

0(2个都在left)

2
3 3

3(2个都在right)
 */